pith. sign in

arxiv: 2510.01852 · v4 · submitted 2025-10-02 · 🧮 math.CO

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

Victoria Ironmonger , Nik Ru\v{s}kuc This is my paper

Pith reviewed 2026-05-18 10:48 UTC · model grok-4.3

classification 🧮 math.CO
keywords well quasi-orderatomicityavoidance setsconsecutive orderscombinatorial structuresgraphsdigraphsrelations
0
0 comments X

The pith

A general framework decides well quasi-order and atomicity for avoidance sets of combinatorial structures under consecutive orders.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a general framework for partially ordered sets of combinatorial structures ordered by consecutive embeddings. It addresses whether the avoidance set defined by a finite set of forbidden substructures is well quasi-ordered, that is, contains no infinite antichains, or atomic, that is, cannot be written as the union of two proper subsets. By extending recent approaches the framework handles a wide class that includes graphs, digraphs and collections of relations. A sympathetic reader cares because these decidability results classify infinite families of structures without having to enumerate every member.

Core claim

We 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.

What carries the argument

The general framework that extends recent approaches to consecutive embedding orders, deciding well quasi-order and atomicity of avoidance sets.

If this is right

  • The framework decides well quasi-order of avoidance sets for any finite forbidden collection in the poset of graphs under consecutive order.
  • It decides atomicity of the same avoidance sets.
  • Both decisions apply directly to digraphs under consecutive order.
  • Both decisions apply directly to collections of relations under consecutive order.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same framework could be tested on consecutive orders for other structures such as permutations or words to see whether the decidability carries over.
  • It connects the two properties of well quasi-order and atomicity through a single set of reduction conditions that future work might simplify further.
  • If the framework is algorithmic, it would yield effective procedures for checking these properties on small forbidden sets.

Load-bearing premise

The consecutive embedding order on the structures permits extending recent approaches into one general framework that covers graphs, digraphs and collections of relations without additional restrictions.

What would settle it

A concrete finite set of forbidden structures on graphs under consecutive order for which the framework fails to decide whether the avoidance set is well quasi-ordered or atomic.

Figures

Figures reproduced from arXiv: 2510.01852 by Nik Ru\v{s}kuc, Victoria Ironmonger.

Figure 1
Figure 1. Figure 1: The graphs G, H and G↾[2,3] respectively from Example 2.1. purposes). We will study posets of relational structures of the same kind under the consecutive order. Given a set X and a partial order ≤ on X, we will denote the poset of X with ≤ by (X, ≤). Throughout this paper, we will take N = {1, 2, 3, . . . } and [1, n] = {1, 2, . . . , n} for n ∈ N. We will take the underlying sets of our relational struct… view at source ↗
Figure 2
Figure 2. Figure 2: Various examples of bicycles. Definition 3.7. A cycle is an in-out cycle if at least one vertex has in-degree > 1 and at least one vertex has out-degree > 1. Definition 3.8. If η, π are paths in a finite digraph, they are related under the subpath order if and only if η is a subpath of π; this is written η ≤ π. Definition 3.9. Let G be a finite digraph. A path complete decomposition of G is a collection of… view at source ↗
Figure 3
Figure 3. Figure 3: The factor graph from Example 5.5 whose paths can create cycles. 1 3 2 4 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The graph corresponding to the path π in Example 5.5 combines σ and ρ. It is clear that Π(θ) = π, so θ ∈ Av(B) and |Σ(π)| ≥ 1. Again note that θ ∈ C because it is of the right structure type and contains no forbidden substructures. □ The following example demonstrates a very natural instance of a poset which is not valid: the poset F of forests under the consecutive order. Example 5.5. Consider the factor … view at source ↗
Figure 5
Figure 5. Figure 5: ΓK from Examples 12.6 and 13.12. rlr lrl rll [PITH_FULL_IMAGE:figures/full_fig_p027_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: ΓK from Examples 13.3 and 13.11. Definition 13.2. Let C = Av(B) be a finitely based avoidance set of double ascents. A left-right bicycle is an induced subgraph of the b-dimensional factor graph ΓAv(W(B)) all of whose vertices are of the form l a r c such that a + c = b. We will see in a moment that, as their name suggests, left-right bicycles are always bicycles. Example 13.3. Consider the avoidance set K… view at source ↗
Figure 8
Figure 8. Figure 8: ΓK from Example 13.13. K = Av(rl), which is precisely the one we saw in [PITH_FULL_IMAGE:figures/full_fig_p031_8.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript develops a general framework for analyzing decidability of well-quasi-ordering and atomicity for avoidance sets of combinatorial structures under consecutive embedding orders. It extends recent approaches to cover a wide class including graphs, digraphs, and collections of relations, providing uniform methods to determine these properties from finite sets of forbidden substructures.

Significance. If the central construction holds, the work supplies a unified, extensible tool for longstanding decidability questions in combinatorial order theory. The consistent inductive arguments on forbidden substructures and absence of hidden uniformity restrictions across the stated classes represent a clear strength, building directly on prior work while broadening its scope.

minor comments (2)
  1. The definition of consecutive embedding is introduced without an early illustrative example; adding a small diagram or concrete instance in the opening definitions section would improve accessibility for readers from adjacent areas of combinatorics.
  2. Notation for the poset of structures and the avoidance set operator is used consistently but could be summarized in a single table or notation box to reduce cross-referencing.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the recognition of the framework's potential for unifying decidability results across graphs, digraphs and relations, and the recommendation of minor revision. The report raises no specific major comments, so we have no individual points to address.

Circularity Check

0 steps flagged

No significant circularity; framework extends prior approaches independently

full rationale

The derivation establishes a general framework for WQO and atomicity questions on avoidance sets under consecutive embeddings by extending recent approaches to a wide class of structures (graphs, digraphs, relation collections). Definitions of consecutive order and inductive arguments on forbidden substructures are developed directly from the poset setup without reducing to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations that force the central claims. The construction remains self-contained, with independent applicability to the stated class and no equations or steps that collapse by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only, no explicit free parameters, axioms, or invented entities are stated; the framework is described at high level without concrete technical assumptions listed.

pith-pipeline@v0.9.0 · 5655 in / 987 out tokens · 38059 ms · 2026-05-18T10:48:28.366621+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 1 internal anchor

  1. [1]

    Atminas, A., Lozin, V., & Moshkov, M. (2017). WQO is decidable for factorial languages. Information and Computation, 256, 321-333

    work page 2017

  2. [2]

    Atminas, A., & Lozin, V. (2024). Deciding atomicity of subword-closed languages. Theoret- ical Computer Science, 1003, 114595

    work page 2024

  3. [3]

    Braunfeld, S. (2018). Infinite limits of finite-dimensional permutation structures, and their automorphism groups: between model theory and combinatorics. arXiv preprint arXiv:1805.04219

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  4. [4]

    Braunfeld, S. (2019). The undecidability of joint embedding and joint homomorphism for hereditary graph classes. Discrete Mathematics & Theoretical Computer Science, 21

    work page 2019

  5. [5]

    Ding, G. (1992). Subgraphs and well-quasi-ordering. Journal of Graph Theory, 16(5), 489- 502

    work page 1992

  6. [6]

    Elizalde, S. (2016). A survey of consecutive patterns in permutations. In Recent trends in combinatorics (pp. 601-618). Cham: Springer International Publishing

    work page 2016

  7. [7]

    Foniok, J., Neˇ setˇ ril, J., & Tardif, C. (2008). Generalised dualities and maximal finite an- tichains in the homomorphism order of relational structures. European Journal of Combi- natorics, 29(4), 881-899

    work page 2008

  8. [8]

    Fra¨ ıss´ e, R. (2000). Theory of relations. Stud. Logic Found. Math. 145. North-Holland Pub- lishing Co., Amsterdam

    work page 2000

  9. [9]

    Higman, G. (1952). Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 3(1), 326-336

    work page 1952

  10. [10]

    Huczynska, S., & Ruˇ skuc, N. (2015). Homomorphic image orders on combinatorial struc- tures. Order, 32(2), 205-226

    work page 2015

  11. [11]

    Huczynska, S., & Ruˇ skuc, N. (2015). Well quasi-order in combinatorics: embeddings and homomorphisms. Surveys in combinatorics, 424, 261-293

    work page 2015

  12. [12]

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

    work page 2024

  13. [13]

    (2017, June)

    Jel´ ınek, V. (2017, June). Ramsey-type and amalgamation-type properties of permutations. In BCC (pp. 272-311)

    work page 2017

  14. [14]

    Kitaev, S. (2011). Patterns in permutations and words (Vol. 1). Heidelberg: Springer

    work page 2011

  15. [15]

    McDevitt, M., & Ruˇ skuc, N. (2021). Atomicity and well quasi-order for consecutive order- ings on words and permutations. SIAM Journal on Discrete Mathematics, 35(1), 495-520

    work page 2021

  16. [16]

    Robertson, N., & Seymour, P. D. (2004). Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2), 325-357

    work page 2004