The $\kappa^+$-Hadwiger conjecture at successors of singular cardinals

Hadwiger's conjecture, that every graph of chromatic number $t$ has the complete graph $K_t$ as a minor, fails outright for uncountable graphs in ZFC (counterexamples of size $2^\kappa$ exist for every infinite $\kappa$, and under GCH this refutes the conjecture at every cardinal). The size-restricted version nevertheless has consistent instances: every graph of size $\kappa$ and chromatic number $\kappa$ having a $K_\kappa$ minor is consistent at $\omega_1$ (from $\mathrm{MA}_{\omega_1}$) and at every successor of a regular cardinal (Uhrik, via the Laver-Shelah special-tree forcing). Uhrik's Theorem 3.4 makes the $\kappa^+$ case equivalent to the tree statement that every tree of size $\kappa^+$ with no $\kappa^+$-branch is $\kappa$-special, and the Laver-Shelah models realize this exactly when $\kappa$ is regular. The single unresolved case is successors of singular cardinals, such as $\aleph_{\omega+1}$: there the Laver-Shelah technique does not reach, no other model is known in which the conjecture holds, and no ZFC refutation is known. The problem is to determine the consistency status of the $\kappa^+$-Hadwiger conjecture at successors of singular cardinals, equivalently of the statement that all branchless trees of size $\kappa^+$ are $\kappa$-special for singular $\kappa$.

Background

Hadwiger's conjecture is a central open problem of finite graph theory: if the chromatic number of a finite graph $G$ is $t$ — the chromatic number being the least number of colors needed for a proper vertex coloring, in which adjacent vertices receive different colors — then the complete graph $K_t$ on $t$ vertices is a minor of $G$, a minor being obtained by deleting vertices and edges and contracting connected subgraphs to single vertices. For infinite graphs the literal generalization fails: there is a countable graph of chromatic number $\omega$ with no $K_\omega$ minor, and the construction extends to every limit cardinal (Proposition 2.2 of Uhrik's paper). Komjáth strengthened this to a robust ZFC failure: for every infinite cardinal $\kappa$ there is a graph of size $2^\kappa$ and chromatic number $\kappa^+$ with no $K_{\kappa^+}$ minor, so under the generalized continuum hypothesis (GCH), where $2^\kappa=\kappa^+$, the conjecture fails at every infinite cardinal. He also proved the first positive size-restricted result: under $\mathrm{MA}_{\omega_1}$ (Martin's axiom at $\aleph_1$, the forcing axiom asserting that every ccc partial order meets any $\aleph_1$ many dense sets), every graph of size and chromatic number $\aleph_1$ contains a subdivision of $K_{\aleph_1}$, a subdivision being obtained by replacing edges with internally disjoint paths. This motivates the $\kappa$-Hadwiger conjecture studied by Uhrik: every graph whose vertex set has cardinality $\kappa$ and whose chromatic number is $\kappa$ has $K_\kappa$ as a minor.

Uhrik's main tool is an equivalence between graph counterexamples and trees. A tree here is a partially ordered set $(T,\leq)$ whose initial segments are well ordered; a branch is a maximal chain, its length being its order type as a well-ordered chain. A tree is $\kappa$-special if it admits a specializing function $f:T\to\kappa$ that is injective on chains; for $\kappa=\omega$ one says simply special. The special tree number $\mathrm{st}$ is the least size of a non-special tree with no uncountable branch, and the uncountable Hadwiger number $\mathrm{hc}$ is the least size of an uncountably chromatic graph (one of chromatic number $>\aleph_0$) with no $K_{\omega_1}$ minor. Building on a construction of Brochet and Diestel that assigns to a graph $G$ a tree $T_G$ reflecting much of its structure, Uhrik proves (Theorem 3.4): for infinite cardinals $\kappa$ and $\lambda$, a graph of size $\lambda$ with chromatic number $\kappa^+$ and no $K_{\kappa^+}$ minor exists if and only if a non-$\kappa$-special tree of size $\lambda$ with no branch of length $\kappa^+$ exists. Consequently $\mathrm{hc}=\mathrm{st}$, and the $\kappa^+$-Hadwiger conjecture is equivalent to the statement that every tree of size $\kappa^+$ with no $\kappa^+$-branch is $\kappa$-special. In the same circle of ideas, Komjáth and Shelah proved independently that every graph on $\kappa>\aleph_0$ vertices contains either an independent set of size $\kappa$ (pairwise non-adjacent vertices) or a topological $K_\kappa$ if and only if $\kappa$ is regular and carries no $\kappa$-Suslin tree (a tree of size $\kappa$ with no chain or antichain of size $\kappa$), and Bowler, Carmesin, Komjáth and Reiher characterized the graphs of colouring number at most $\mu$ — the colouring number being the least cardinal $\mu$ such that the vertices admit a well order in which each vertex has fewer than $\mu$ earlier neighbors, an upper bound for the chromatic number — by excluded subgraphs; both results delimit how far Hadwiger-type statements can hold at uncountable cardinals.

For the consistency direction, Uhrik applies the forcing technique that Laver and Shelah developed for the $\aleph_2$-Souslin hypothesis: from a regular $\kappa$ one obtains a model in which every tree of size $\kappa^+$ without a $\kappa^+$-branch is $\kappa$-special, and hence (Theorem 6.2) the $\kappa^+$-Hadwiger conjecture holds. The technique does not reach successors of singular cardinals such as $\aleph_{\omega+1}$: the Laver-Shelah construction explicitly leaves those cardinals as an exception. The adjacent, very active program on the tree property at successors of singular cardinals — the assertion that there are no $\kappa^+$-Aronszajn trees, i.e. trees of height $\kappa^+$, levels of size below $\kappa^+$, and no cofinal branch, together with its strengthenings — produces such models from large cardinals, but those statements are weaker than what the Hadwiger equivalence demands: they do not give a specializing function for every branchless tree of size $\kappa^+$, and they say nothing about wide trees with large levels. Thus the successor-of-singular case is open from both directions: no model is known in which the $\kappa^+$-Hadwiger conjecture holds for singular $\kappa$, and no ZFC argument is known that refutes it there.

Problem Statement

Fix a singular cardinal $\kappa$; the canonical test case is $\kappa=\aleph_\omega$, so $\kappa^+=\aleph_{\omega+1}$. Determine the consistency status at successors of singular cardinals of the $\kappa^+$-Hadwiger conjecture

$H(\kappa^+):\ \text{every graph } G \text{ with } |G|=\chi(G)=\kappa^+ \text{ has a } K_{\kappa^+} \text{ minor},$

which by Uhrik's Theorem 3.4 is equivalent to the tree statement

$\text{every tree of size } \kappa^+ \text{ with no branch of length } \kappa^+ \text{ is } \kappa\text{-special}.$

The determination is whether $H(\kappa^+)$ is consistent at successors of singular cardinals — there is a model of ZFC, from whatever large cardinal hypotheses are needed, in which $H(\kappa^+)$ holds at some or all successors of singular cardinals, equivalently one in which every branchless tree of size $\kappa^+$ is $\kappa$-special — or refuted in ZFC, that is, there is a proof that for some singular $\kappa$ there exists a graph of size $\kappa^+$ with chromatic number $\kappa^+$ and no $K_{\kappa^+}$ minor, equivalently a non-$\kappa$-special tree of size $\kappa^+$ with no $\kappa^+$-branch. The status may be determined for a single singular $\kappa$ (canonically $\kappa=\aleph_\omega$), for several singular cardinals, or for the singular cardinals split by cofinality class. This is the last open entry in the consistency classification of the size-restricted Hadwiger conjecture over uncountable cardinals: limit cardinals never satisfy it, GCH refutes it at every infinite cardinal, $\omega_1$ and successors of regular cardinals consistently satisfy it, and successors of singular cardinals are the unsettled case.

References

1. Dávid Uhrik, The Uncountable Hadwiger Conjecture and Characterizations of Trees Using Graphs, arXiv:2212.02169 (2022), DOI 10.48550/arXiv.2212.02169, https://arxiv.org/abs/2212.02169
2. D. Uhrik, The uncountable Hadwiger conjecture and characterizations of trees using graphs, Acta Mathematica Hungarica 172(1):19-33 (2024), DOI 10.1007/s10474-024-01399-x, https://doi.org/10.1007/s10474-024-01399-x
3. Péter Komjáth, Hadwiger's conjecture for uncountable graphs, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 87(2):337-341 (2017), DOI 10.1007/s12188-016-0170-1, https://doi.org/10.1007/s12188-016-0170-1
4. Richard Laver and Saharon Shelah, The $\aleph_2$-Souslin hypothesis, Transactions of the American Mathematical Society 264(2):411-417 (1981), DOI 10.2307/1998547, https://doi.org/10.2307/1998547
5. Corey Bacal Switzer, The special tree number, Fundamenta Mathematicae 262(2):129-151 (2023), DOI 10.4064/fm180-1-2023, https://doi.org/10.4064/fm180-1-2023 (preprint arXiv:2203.04186, https://arxiv.org/abs/2203.04186)
6. Péter Komjáth and Saharon Shelah, Monocolored topological complete graphs in colorings of uncountable complete graphs, Acta Mathematica Hungarica 163(1):71-84 (2021), DOI 10.1007/s10474-020-01125-3, https://doi.org/10.1007/s10474-020-01125-3
7. J.-M. Brochet and R. Diestel, Normal tree orders for infinite graphs, Transactions of the American Mathematical Society 345(2):871-895 (1994), DOI 10.2307/2155004, https://doi.org/10.2307/2155004
8. Max Pitz, Applications of order trees in infinite graphs, Order 41(1):65-81 (2024), DOI 10.1007/s11083-022-09601-x, https://doi.org/10.1007/s11083-022-09601-x
9. Nathan Bowler, Johannes Carmesin, Péter Komjáth and Christian Reiher, The Colouring Number of Infinite Graphs, Combinatorica 39(6):1225-1235 (2019), DOI 10.1007/s00493-019-4045-9, https://doi.org/10.1007/s00493-019-4045-9
10. William Adkisson, Tree Properties at Successors of Singulars of Many Cofinalities, arXiv:2502.01762 (2025), DOI 10.48550/arXiv.2502.01762, https://arxiv.org/abs/2502.01762