Well-quasi-ordering countable Cayley graphs under the minor relation and its refinements (Conjecture 5.1 and Question 5.2 of 'A full Halin grid theorem')

The paper 'A full Halin grid theorem' by Georgakopoulos and Hamann poses two linked open problems about quasi-ordering infinite, highly symmetric graphs: Conjecture 5.1 asks whether the countable Cayley graphs are well-quasi-ordered under the minor relation — the Cayley-graph special case of Thomas's 1989 conjecture that all countable graphs are; Question 5.2 asks for which finer relations (shallow minors, coarse embeddability, diverging subdivisions, diverging embeddings) the class of countable Cayley graphs remains well-quasi-ordered. As of the latest verified literature (late 2025), the one-ended case is settled in a strong form, the multi-ended accessible case of Conjecture 5.1 is open, coarse embeddability already fails well-quasi-ordering via an antichain of finitely presented Cayley graphs communicated by Kropholler, and the diverging-subdivision case is singled out as the most interesting open refinement.

Background

A graph $G$ is a minor of a graph $H$ if $G$ is obtained from a subgraph of $H$ by contracting connected subgraphs to single vertices. A class of graphs is well-quasi-ordered (wqo) under a relation if it contains neither an infinite antichain (pairwise incomparable graphs) nor an infinite strictly descending chain, i.e. an infinite sequence $G_1>G_2>\cdots$ in which each graph is a proper minor of its predecessor; equivalently, in every infinite sequence of graphs from the class, some earlier graph is below some later one. The Graph Minor Theorem of Robertson and Seymour establishes wqo of all finite graphs under the minor relation, and Robin Thomas later conjectured the analogous statement for countable graphs; this infinite version remains one of the central open problems of structural graph theory.

A Cayley graph is the graph of a group: its vertices are the elements of a group $\Gamma$ given with a generating set $S$ , with an edge joining $g$ to $gs$ for each $g$ in $\Gamma$ and $s$ in $S$ ; for a countable group this is a countable graph, locally finite — meaning every vertex has only finitely many neighbours — exactly when $S$ is finite. Georgakopoulos and Hamann proposed, as a special case of Thomas's conjecture that 'may be within reach', that the countable Cayley graphs are wqo under the minor relation (Conjecture 5.1 of their paper). Three facts settle the one-ended case. An end of an infinite graph is an equivalence class of rays (one-way infinite paths), two rays being equivalent when no finite vertex set separates them; the degree of an end is the maximum number of pairwise disjoint rays it contains (an end is thick when this degree is infinite), and a Cayley graph of a group has one, two, or infinitely many ends. Thomassen proved that every locally finite, one-ended, non-planar, vertex-transitive graph — vertex-transitive meaning that every vertex can be carried to every other by an automorphism of the graph — contains the infinite complete graph $K_\infty$ (the complete graph on countably many vertices) as a minor; on the other hand every one-ended planar graph is a minor of the hexagonal grid (aka the honeycomb lattice $\mathbb{H}$ : the infinite planar graph in which every face is a hexagon and every vertex has degree three). Combined with their full Halin grid theorem, this yields exactly two minor-twin classes — two graphs are minor-twins if each is a minor of the other, an equivalence relation — of locally finite one-ended vertex-transitive graphs, namely that of the hexagonal grid and that of the cubic grid $\mathbb{Z}^3$ (the standard square grid in three dimensions). Moreover, Esperet, Giocanti and Legrand-Duchesne proved that a Cayley graph with arbitrarily large finite clique minors already contains a $K_\infty$ minor, so every inaccessible Cayley graph carries $K_\infty$ (a graph is accessible if it can be reduced to a finite graph by iteratively removing finite vertex separators); hence Conjecture 5.1 reduces to accessible graphs. The remaining obstruction is the multi-ended accessible case: the paper exhibits arbitrarily long strictly descending chains of two-ended Cayley graphs — for each $k$ the graphs $C_{k-i+3}\times\mathbb{Z}$ for $1\le i\le k$ , where $C_n$ is the cycle on $n$ vertices and $\mathbb{Z}$ is the two-way infinite path — and expects, but cannot prove, that for each $n$ there are only finitely many minor-twin classes of two-ended Cayley graphs whose ends have degree $n$ . For the tree-like case, meaning graphs with no thick end, the classical theorem of Nash-Williams that infinite trees are wqo under the topological minor relation — $G$ is a topological minor of $H$ if some subdivision of $G$ , obtained by replacing edges with internally disjoint paths, is a subgraph of $H$ — is the envisioned tool.

The same section poses Question 5.2: replace the minor relation by a finer one and ask again for wqo. The relations considered are: the shallow minor relation $<_{sh}$ , defined like the minor relation except that the branch sets (the connected subgraphs contracted to single vertices) must have uniformly bounded size; the coarse-embeddability relation $<_{c}$ , where $G<_{c}H$ if there is a coarse embedding of $G$ into $H$ , i.e. a map whose distance distortion is controlled by a fixed function in both directions; the diverging-subdivision relation $<_{div}$ , where $G<_{div}H$ if $H$ contains a subdivision of $G$ whose branch vertices diverge, meaning that vertices of the model that are far apart map to vertices of $H$ that are far apart; and the analogous diverging-embedding relation, in which $G$ is below $H$ if there is a diverging map from $G$ into $H$ , that is, a map $f$ such that $d_H(f(x_i),f(y_i))\to\infty$ whenever $d_G(x_i,y_i)\to\infty$ . The motivation for the refinements is that, in the authors' words, even a proof of Conjecture 5.1 'seems too weak to have any group-theoretic consequences', whereas relations stable under changing the generating set, such as $<_{c}$ and $<_{div}$ , could connect graph minor theory to geometric group theory. Already the $<_{c}$ case fails: an infinite $<_{c}$ -antichain among Cayley graphs of finitely presented groups — groups given by finitely many generators and finitely many defining relations, hence finitely generated — was communicated to the authors by Robert Kropholler (unpublished private communication, reported in the source paper), which is why the authors single out $<_{div}$ as the particularly interesting open case of Question 5.2.

Problem Statement

Determine the well-quasi-ordering behaviour of the class of countable Cayley graphs under the minor relation and its refinements, as posed in Section 5 of 'A full Halin grid theorem' (Georgakopoulos and Hamann). Part (i), Conjecture 5.1: prove that the countable Cayley graphs are well-quasi-ordered under the minor relation — that is, in every infinite sequence of Cayley graphs of countable groups (with arbitrary generating sets), some earlier graph is a minor of some later one — or refute it by an explicit infinite antichain or infinite strictly descending chain of such Cayley graphs. Part (ii), Question 5.2: for each of the finer relations on graphs — the shallow minor relation $<_{sh}$ , the coarse-embeddability relation $<_{c}$ , the diverging-subdivision relation $<_{div}$ , and the diverging-embedding relation — determine whether the class of countable Cayley graphs is well-quasi-ordered, by a proof or by an explicit infinite antichain or descending chain. The coarse-embeddability case is already answered negatively by an antichain of finitely presented Cayley graphs reported in the source paper; the diverging-subdivision relation is the refinement the source authors single out as most interesting. Parts (i) and (ii) share one scientific objective: establishing (or delimiting) a Robertson–Seymour-style well-quasi-ordering theorem for the fundamental class of Cayley graphs under minor-type relations.

References

A. Georgakopoulos and M. Hamann, 'A full Halin grid theorem', Discrete and Computational Geometry 75(4):1060-1072 (2024), DOI: 10.1007/s00454-024-00707-0; arXiv:2403.05862, https://arxiv.org/abs/2403.05862
A. Georgakopoulos, 'On better-quasi-ordering under graph minors', arXiv:2510.19285 (2025), https://arxiv.org/abs/2510.19285
S. Albrechtsen and M. Hamann, 'A coarse Halin Grid Theorem with applications to quasi-transitive, locally finite graphs', arXiv:2507.12973 (2025, v2 2026), https://arxiv.org/abs/2507.12973
S. Albrechtsen and M. Hamann, 'Asymptotic half-grid and full-grid minors', arXiv:2412.15675 (2024, v3 2025), https://arxiv.org/abs/2412.15675
R. Thomas, 'Well-quasi-ordering infinite graphs with forbidden finite planar minor', Transactions of the American Mathematical Society 312(1):279-313 (1989), DOI: 10.1090/S0002-9947-1989-0932450-9, https://doi.org/10.1090/S0002-9947-1989-0932450-9
N. Robertson and P. D. Seymour, 'Graph Minors. XX. Wagner's conjecture', Journal of Combinatorial Theory, Series B 92(2):325-357 (2004), DOI: 10.1016/j.jctb.2004.08.001, https://doi.org/10.1016/j.jctb.2004.08.001
C. Thomassen, 'The Hadwiger number of infinite vertex-transitive graphs', Combinatorica 12:481-491 (1992), DOI: 10.1007/BF01305240, https://doi.org/10.1007/BF01305240
C. St. J. A. Nash-Williams, 'On well-quasi-ordering infinite trees', Mathematical Proceedings of the Cambridge Philosophical Society 61:697-720 (1965), DOI: 10.1017/S0305004100039062, https://doi.org/10.1017/S0305004100039062
L. Esperet, U. Giocanti, and C. Legrand-Duchesne, 'The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem', Journal of Combinatorial Theory, Series B 169:561-613 (2024), DOI: 10.1016/j.jctb.2024.08.002; arXiv:2304.01823, https://arxiv.org/abs/2304.01823
T. Nguyen, A. Scott, and P. Seymour, 'A counterexample to the coarse Menger conjecture', arXiv:2401.06685 (2024), https://arxiv.org/abs/2401.06685