On better-quasi-ordering under graph minors

Agelos Georgakopoulos · 2025

Read On better-quasi-ordering under graph minors by Agelos Georgakopoulos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19285.txt.

Introduction

Agelos Georgakopoulos links two open problems in graph theory. Both concern ordering graphs by the minor relation. A graph counts as smaller if it can be had by shrinking another. It can also be had by deleting parts. Thomas conjectured that countable graphs are well-quasi-ordered under minors. That claim is still open.

Georgakopoulos restricts to graphs with no infinite paths. In that world, the conjecture matches a second open problem. Finite graphs must be better-quasi-ordered. He proves the second claim would imply the first, in stronger form. He also gives several equivalent versions of both claims.

Catalog record

CREATORAgelos Georgakopoulos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE139 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19285

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On better-quasi-ordering under graph minors Agelos Georgakopoulos Abstract In the aftermath of the Robertson–Seymour Graph Minor Theorem, Thomas conjectured that the countable graphs are well-quasi-ordered under the minor relation. We prove that this conjecture, when restricted to graphs with no infinite paths (rays), is equivalent to the statement that the finite graphs are better-quasi-ordered, another well-known open problem. Even more, we prove that the latter implies that the countable rayless graphs are better-quasi-ordered. We prove several other statements to be equivalent to the above, one of which being that the rayless countable graphs of rank α \alpha can be decomposed into exactly ℵ 0 \aleph_{0} minor-twin classes for every ordinal α < ω 1 \alpha<\omega_{1} . By restricting the latter statement to trees, and combining it with Nash-Williams’ theorem that the infinite trees are well-quasi-ordered, we deduce as a side result that a minor-closed family of ℕ \mathbb{N} -labelled rayless forests is Borel —in the Tychonoff product topology— if and only if it does not contain all rayless forests. As another side-result, we prove Seymour’s self-minor conjecture for rayless graphs of any cardinality. Keywords: graph minor, well-quasi-order, better-quasi-order, countable rayless graph, Borel set, self-minor conjecture. MSC 2020 Classification: 05C83, 05C63, 06A07. 1 Introduction The celebrated Robertson–Seymour Graph Minor Theorem [ 20 ] – [ 21 ] states that the finite graphs are well-quasi-ordered under the minor relation < . This paper focuses on two well-known problems that it left open: Conjecture 1.1 (Folklore [ 5 , 17 ] ) . The finite graphs are better-quasi-ordered (BQO) under the minor relation. Conjecture 1.2 (Thomas’ conjecture [ 25 ] ) . The countable graphs are well-quasi-ordered (WQO) under the minor relation. While WQO is a simple notion, its strengthening BQO is much harder to define but has the benefit of being preserved by natural operations that occur in inductive arguments, making it an indispensable tool even when one is only interested to prove that an order is WQO; this idea has found applications in several areas including combinatorics [ 15 , 26 ] , order theory [ 13 ] , set theory [ 14 ] and topology [ 3 ] . See [ 17 ] for a survey of these notions. According to Pequignot [ 17 ] , the poset of finite graphs endowed with the minor relation is “the only naturally occurring WQO which is not yet known to be BQO”. A graph is rayless , if it does not contain an (1-way) infinite path. The first main result of this paper provides a strong connection between the above conjectures, and much more: Theorem 1.1 . The following statements are equivalent: (i) The finite graphs are BQO; (ii) The countable rayless graphs are WQO; (iii) The countable rayless graphs are BQO. Thus we have reduced the better-quasi-ordering of the finite graphs to a comparatively simple statement about infinite graphs. Commenting on Thomas’ Conjecture 1.2 and similar questions, Robertson, Seymour & Thomas [ 19 ] wrote: “There is not much chance of proving these conjectures because they imply that the set of all finite graphs is ‘second-level better-quasi-ordered’ by minor containment, which in itself seems to be a hopelessly difficult problem”. The (easier) implication (ii) \to (i) of Theorem 1.1 provides a far reaching strengthening of this claim: it says that the words ‘second-level’ can be deleted. Moreover, the implication (ii) \to (iii) is a considerable strengthening. Interestingly, the proof of the latter implication passes via the implication (ii) \to (i) . Part of this proof applies to arbitrary quasi-orders (Corollary 11.8 ). Our most difficult result is the implication (i) \to (ii) . While the above quote seems as timely as ever, the results of this paper provide new tools for attacking Conjectures 1.1 and 1.2 , and point out interesting special cases. See Section 12 for more. But let me first try to explain the above quote. What is meant by ‘second-level better-quasi-ordered’ here is probably the following. Given two sets of graphs \mathcal{G},\mathcal{G}^{\prime} , we write \mathcal{G}<_{*}\mathcal{G}^{\prime} if for every G\in\mathcal{G} there is H\in\mathcal{G}^{\prime} such that G<H . Note that <_{*} is a quasi-order on the powerset \mathcal{P}(\mathcal{F}) of the class \mathcal{F} of finite graphs. Problem 1.3 . Are the sets of finite graphs well-quasi-ordered under <_{*} ? An equivalent formulation is whether the set of minor-closed families of finite graphs is well-quasi-ordered by the inclusion relation. The connection between Problem 1.3 and Conjecture 1.1 is that one can take the definition of <_{*} further, and extend it from an ordering of \mathcal{P}(\mathcal{F}) into an ordering of \mathcal{P}(\mathcal{P}(\mathcal{F})) , and iterate transfinitely in order to define better-quasi-ordering; see Section 2.4 for details. In particular, our Theorem 1.1 implies that if Thomas’ Conjecture 1.2 has a positive answer, then so does Problem 1.3 . Motivated by Theorem 1.1 , we undertake a thorough study of Thomas’ conjecture for rayless graphs, noting that some long-standing open problems for infinite graphs have been settled in the rayless case [ 1 , 2 , 18 ] . As a warm-up, we will prove Seymour’s (unpublished) self-minor conjecture for rayless graphs of any cardinality, which to the best of my knowledge was open even for countable graphs: Corollary 1.2 . For every infinite rayless graph G , there is a minor model of G\ in itself which is not the identity. (Oporowski [ 16 ] has found uncountable counterexamples to Seymour’s self-minor conjecture, which of course contain rays.) A well-known equivalent way to define what it means for a quasi-order (Q,\leq) to be well-quasi-ordered is to say that it has no infinite antichain and no infinite descending chain. None of these conditions implies the other in general, but we will show that in our setup they are in fact equivalent. Let \mathcal{R} denote the class of countable rayless graphs. Our second main result can be summarized as follows: Theorem 1.3 . The following statements are equivalent: (a) \mathcal{R} is well-quasi-ordered; (b) \mathcal{R} has no infinite descending chain; (c) \mathcal{R} has no infinite antichain; (d) for every ordinal \alpha<\omega_{1} , the number of minor-twin classes of countable rayless graphs of rank \alpha is \aleph_{0} . As a consequence, to prove that \mathcal{R} is well-quasi-ordered, it would suffice to prove that the rayless graphs of rank \alpha are well-quasi-ordered for every ordinal \alpha<\omega_{1} . But the most interesting aspect of Theorem 1.3 is the equivalence of the well-quasi-ordering of \mathcal{R} to the cardinality condition (d) , which I will now explain. We say that two graphs G,H are minor-twins , if both G<H and H<G hold. Each rayless graph can be assigned an ordinal number, called its rank , by recursively decomposing G\ into graphs of smaller ranks (Section 2.3 ) similarly to the definition of rank for Borel sets or Hausdorff rank for linear orders. It is known that every ordinal \alpha smaller that the least uncountable ordinal \omega_{1} is the rank of some countable graph G . Assuming \neg\mathrm{CH} , i.e. that \aleph_{1}<2^{\aleph_{0}} , an alternative way to formulate (d) is to say that \mathcal{R} consists of exactly \aleph_{1} minor-twin equivalence classes. We will prove a refinement of Theorem 1.3 (Theorem 9.1 ) whereby \mathcal{R} is replaced by the subclass of graphs of (up

Read the complete text