Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Well quasi-order and ...
Article

Well quasi-order and atomicity for combinatorial structures under consecutive orders

Victoria Ironmonger (1), Nik Ruškuc ORCID (1)
(1) University of St Andrews
Download article
Open on arXiv
Submitted on
November 12, 2025
Accepted on
June 19, 2026
Published on
July 9, 2026
Last modified on
July 9, 2026
Special issue 28
vol. 28:1, Permutation Patterns 2025
Special issues
DOI
10.46298/dmtcs.16905
License
Attribution 4.0 International (CC BY 4.0)
Indicators
187
Views
75
Downloads

Well quasi-order and atomicity for combinatorial structures under consecutive orders

Victoria Ironmonger (1), Nik Ruškuc ORCID (1)
(1) University of St Andrews
Abstract
We consider partially ordered sets of combinatorial structures under consecutive orders, meaning that two structures are related when one embeds in the other such that `consecutive' elements remain consecutive in the image. Given such a partially ordered set, we may ask decidability questions about its avoidance sets: subsets defined by a finite number of forbidden substructures. Two such questions ask, given a finite set of structures, whether its avoidance set is well quasi-ordered (i.e. contains no infinite antichains) or atomic (i.e. cannot be expressed as the union of two proper subsets). Extending some recent new approaches, we will establish a general framework, which enables us to answer these problems for a wide class of combinatorial structures, including graphs, digraphs and collections of relations.
Keywords
  • Combinatorics
  • 06A07, 05C20, 05C38, 03C13
Mathematics Subject Classification 2020
  • 03C99 - Model theory
  • 05C20 - Directed graphs (digraphs), tournaments
  • 05C38 - Paths and cycles
  • 06A07 - Combinatorics of partially ordered sets
Preview
Loading PDF preview...
References

  1. J.-P. Allouche and J. Shallit. Automatic sequences. Cambridge University Press, Cambridge, 2003. ISBN 0-521-82332-3.

    DOI : 10.1017/CBO9780511546563

  2. A. Atminas and V. Lozin. Deciding atomicity of subword-closed languages. Theoret. Comput. Sci., 1003: Paper No. 114595, 2024.

    DOI : 10.1016/j.tcs.2024.114595

  3. A. Atminas, V. Lozin, and M. Moshkov. WQO is decidable for factorial languages. Inform. and Comput., 256:321-333, 2017.

    DOI : 10.1016/j.ic.2017.08.001

  4. S. Braunfeld. The undecidability of joint embedding and joint homomorphism for hereditary graph classes. Discrete Math. Theor. Comput. Sci., 21(2): Paper No. 9, 17, 2019.

    DOI : 10.23638/dmtcs-21-2-9

  5. S. Braunfeld. The undecidability of joint embedding for 3-dimensional permutation classes. Discrete Math. Theor. Comput. Sci., 22(2): Paper No. 10, 2021.

    DOI : 10.46298/dmtcs.6165

  6. G. Ding. Subgraphs and well-quasi-ordering. J. Graph Theory, 16(5):489-502, 1992.

    DOI : 10.1002/jgt.3190160509

  7. S. Elizalde. A survey of consecutive patterns in permutations. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 601-618. Springer, [Cham], 2016.

    DOI : 10.1007/978-3-319-24298-9_24

  8. J. Foniok, J. Nešetřil, and C. Tardif. Generalised dualities and maximal finite antichains in the homo- morphism order of relational structures. European J. Combin., 29(4):881-899, 2008.

    DOI : 10.1016/j.ejc.2007.11.017

  9. R. Fraïssé. Theory of relations, volume 145 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, revised edition, 2000. ISBN 0-444-50542-3. With an appendix by Norbert Sauer.

    DOI : 10.1112/plms/s3-2.1.326

  10. G. Higman. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326-336, 1952.

    DOI : 10.1112/plms/s3-2.1.326

  11. S. Huczynska and N. Ruškuc. Homomorphic image orders on combinatorial structures. Order, 32(2): 205-226, 2015.

    DOI : 10.1007/s11083-014-9326-8

  12. S. Huczynska and N. Ruškuc. Well quasi-order in combinatorics: embeddings and homomorphisms. In Surveys in combinatorics 2015, volume 424 of London Math. Soc. Lecture Note Ser., pages 261-293. Cambridge Univ. Press, Cambridge, 2015.

    DOI : 10.1017/cbo9781316106853.009

  13. V. Ironmonger. Well quasi-order and atomicity for combinatorial structures. PhD thesis, University of St Andrews, 2026.

    DOI : 10.46298/dmtcs.16905

  14. V. Ironmonger and N. Ruškuc. Decidability of well quasi-order and atomicity for equivalence relations under embedding orderings. Order, 41(3):761-786, 2024.

    DOI : 10.1007/s11083-024-09659-9

  15. V. Jelínek. Ramsey-type and amalgamation-type properties of permutations. In Surveys in combinatorics 2017, volume 440 of London Math. Soc. Lecture Note Ser., pages 272-311. Cambridge Univ. Press, Cambridge, 2017. ISBN 978-1-108-41313-8.

    DOI : 10.1017/9781108332699.007

  16. S. Kitaev. Patterns in permutations and words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, 2011. ISBN 978-3-642-17332-5; 978-3-642-17333-2. With a fore- word by Jeffrey B. Remmel.

    DOI : 10.1007/978-3-642-17333-2

  17. M. McDevitt and N. Ruškuc. Atomicity and well quasi-order for consecutive orderings on words and permutations. SIAM J. Discrete Math., 35(1):495-520, 2021.

    DOI : 10.1137/20m1338411

  18. N. Robertson and P. D. Seymour. Graph minors. XX. Wagner's conjecture. J. Combin. Theory Ser. B, 92(2):325-357, 2004.

    DOI : 10.1016/j.jctb.2004.08.001