{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T07:00:53Z","timestamp":1772521253422,"version":"3.50.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:00:00Z","timestamp":1707868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:00:00Z","timestamp":1707868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the posets of equivalence relations on finite sets under the standard embedding ordering and under the consecutive embedding ordering. In the latter case, the relations are also assumed to have an underlying linear order, which governs consecutive embeddings. For each poset we ask the well quasi-order and atomicity decidability questions: Given finitely many equivalence relations <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\rho _1,\\dots ,\\rho _k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03c1<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>\u03c1<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, is the downward closed set <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\textrm{Av}\\,}}(\\rho _1,\\dots ,\\rho _k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>Av<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>\u03c1<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>\u03c1<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> consisting of all equivalence relations which do not contain any of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\rho _1,\\dots ,\\rho _k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03c1<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>\u03c1<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>: (a) well-quasi-ordered, meaning that it contains no infinite antichains? and (b) atomic, meaning that it is not a union of two proper downward closed subsets, or, equivalently, that it satisfies the joint embedding property?<\/jats:p>","DOI":"10.1007\/s11083-024-09659-9","type":"journal-article","created":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T07:02:18Z","timestamp":1707894138000},"page":"761-786","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Decidability of Well Quasi-Order and Atomicity for Equivalence Relations Under Embedding Orderings"],"prefix":"10.1007","volume":"41","author":[{"given":"V.","family":"Ironmonger","sequence":"first","affiliation":[]},{"given":"N.","family":"Ru\u0161kuc","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,14]]},"reference":[{"key":"9659_CR1","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.ic.2017.08.001","volume":"256","author":"A Atminas","year":"2017","unstructured":"Atminas, A., Lozin, V., Moshkov, M.: WQO is decidable for factorial languages. Inform. Comput. 256, 321\u2013333 (2017)","journal-title":"Inform. Comput."},{"issue":"9","key":"9659_CR2","first-page":"17","volume":"21","author":"S Braunfeld","year":"2019","unstructured":"Braunfeld, S.: The undecidability of joint embedding and joint homomorphism for hereditary graph classes. Discrete Math. Theor. Comput. Sci. 21(9), 17 (2019)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"10","key":"9659_CR3","first-page":"20","volume":"22","author":"S Braunfeld","year":"2021","unstructured":"Braunfeld, S.: The undecidability of joint embedding for 3-dimensional permutation classes. Discrete Math. Theor. Comput. Sci. 22(10), 20 (2021)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9659_CR4","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1016\/j.disc.2011.03.014","volume":"311","author":"G Cherlin","year":"2011","unstructured":"Cherlin, G.: Forbidden substructures and combinatorial dichotomies: WQO and universality. Discrete Math. 311, 1543\u20131584 (2011)","journal-title":"Discrete Math."},{"key":"9659_CR5","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1002\/jgt.3190160509","volume":"16","author":"G Ding","year":"1992","unstructured":"Ding, G.: Subgraphs and well quasi-ordering. J. Graph Theory 16, 489\u2013502 (1992)","journal-title":"J. Graph Theory"},{"key":"9659_CR6","doi-asserted-by":"crossref","unstructured":"Elizalde, S.: A survey of consecutive patterns in permutations. Recent trends in combinatorics, 601\u2013618, IMA Vol. Math. Appl. 159, Springer, (2016)","DOI":"10.1007\/978-3-319-24298-9_24"},{"key":"9659_CR7","doi-asserted-by":"crossref","unstructured":"Elizalde, S., McNamara, P.R.W.: The structure of the consecutive pattern poset. Int. Math. Res. Not. IMRN, 2099\u20132134 (2018)","DOI":"10.1093\/imrn\/rnw293"},{"key":"9659_CR8","unstructured":"Fra\u00efss\u00e9, R.: Theory of relations. Stud. Logic Found. Math. 145, North-Holland Publishing Co., Amsterdam (2000)"},{"key":"9659_CR9","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"2","author":"G Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 2, 326\u2013336 (1952)","journal-title":"Proc. London Math. Soc."},{"key":"9659_CR10","volume-title":"Model theory, Encyclopedia of Mathematics and its Applications 42","author":"W Hodges","year":"1993","unstructured":"Hodges, W.: Model theory, Encyclopedia of Mathematics and its Applications 42. CUP, Cambridge (1993)"},{"key":"9659_CR11","doi-asserted-by":"crossref","unstructured":"Huczynska, S., Ru\u0161kuc, N.: Well quasi-order in combinatorics: embeddings and homomorphisms, Surveys in combinatorics 2015, 261\u2013293, LMS Lecture Note Ser. 424, CUP, Cambridge (2015)","DOI":"10.1017\/CBO9781316106853.009"},{"key":"9659_CR12","doi-asserted-by":"crossref","unstructured":"Liu, C-H.: Recent progress on well-quasi-ordering graph, Well-quasi orders in computation, logic, language and reasoning\u2014a unifying concept of proof theory, automata theory, formal languages and descriptive set theory, 161\u2013188, Trends Log. Stud. Log. Libr., 53, Springer, Cham (2020)","DOI":"10.1007\/978-3-030-30229-0_7"},{"issue":"1","key":"9659_CR13","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1137\/20M1338411","volume":"35","author":"M McDevitt","year":"2021","unstructured":"McDevitt, M., Ru\u0161kuc, N.: Atomicity and well quasi-order for consecutive orderings on words and permutations. SIAM J. Discrete Math. 35(1), 495\u2013520 (2021)","journal-title":"SIAM J. Discrete Math."},{"key":"9659_CR14","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Combin. Theory Ser. B 92, 325\u2013357 (2004)","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"9659_CR15","unstructured":"Vatter, V.: Permutation classes, Handbook of enumerative combinatorics, 753\u2013833, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL (2015)"}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-024-09659-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11083-024-09659-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-024-09659-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:10:16Z","timestamp":1736406616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11083-024-09659-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,14]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9659"],"URL":"https:\/\/doi.org\/10.1007\/s11083-024-09659-9","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"value":"0167-8094","type":"print"},{"value":"1572-9273","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,14]]},"assertion":[{"value":"10 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}