pith. sign in

arxiv: 2510.01852 · v5 · pith:NNX6FRHNnew · 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.