WorksMathematics
A ZFC counterexample to Taylor's conjecture on finite subgraphs
Abstract
We construct, in ZFC, a graph of chromatic number such that every graph whose finite ordinary subgraphs embed into has chromatic number at most . Taking the target chromatic number to be gives a negative answer to Taylor's conjecture on finite subgraphs. The construction uses hereditarily countable vertex data, finite coordinate inequalities, and a countable-closure reflection argument. A compactness argument transfers the resulting finite coloring properties to the entire finite age of .
Introduction
All graphs in this paper are simple and undirected. An embedding of a graph into a graph is an injective map on vertices that preserves adjacency. Write for the class of finite graphs that embed into , up to isomorphism. The chromatic number is the least cardinality of a set admitting a proper coloring of .
A conjecture of Walter Taylor, recorded by [2], asks whether every graph with has the following property. For every cardinal , there is a graph with
Komjáth and Shelah [3] proved that a negative answer is consistent with ZFC. The theorem below gives a counterexample in ZFC itself. Throughout, put .
Theorem 1.1. There is a graph with such that, for every graph ,
Consequently, (1.1) fails for this and .
The host construction is based on Lambie-Hanson’s work on the growth of chromatic numbers of finite subgraphs [4], in particular his construction using hereditarily countable structures [5]. We give the construction and all the properties needed for (1.2). The argument uses one chosen predecessor at each natural-number label and increasing bounds on the lengths of odd closed walks in the label tails.
We use . A closed walk of length is a sequence with consecutive vertices adjacent. Vertices may repeat. A coloring makes a walk monochromatic when all its vertices receive the same color. We work throughout in ZFC.
A compactness criterion for the finite age
Proposition 2.1. Suppose that, for each , a graph admits a coloring into a finite nonempty set such that no odd closed walk of length at most is monochromatic under . If , then .
Proof. Fix . Give the discrete topology and consider the compact space
For every odd closed walk of of length at most , let be the set of colorings in that make nonmonochromatic. Each is clopen because membership depends on finitely many coordinates.
A finite collection of these conditions involves a finite set . The finite graph embeds into . Pulling back along such an embedding colors and satisfies every condition in the collection. Indeed, an adjacency-preserving map sends each of the specified closed walks to a closed walk of the same length. Extend the coloring arbitrarily to the other vertices of . Thus the sets have the finite intersection property. Compactness gives a coloring
for which no odd closed walk of length at most is monochromatic. This is the usual finite-color compactness principle underlying the de Bruijn–Erdős theorem [1].
Choose such a for every and set
Every fiber of induces a graph with no odd closed walk. Otherwise a walk of odd length in a fiber would be monochromatic under for any with .
A graph with no odd closed walk is bipartite. To see this, choose a root in each connected component and color a vertex by the parity of a path from the root. Two such paths have the same parity, since concatenating one with the reverse of the other gives a closed walk, which must have even length. Adjacent vertices have opposite parity. Choose a binary coloring on each fiber of , and denote the resulting bit at by .
The map is a proper coloring of . Its color set has cardinality at most . In fact, each finite embeds into , so
A finite coordinate obstruction
For a positive integer , define
If and are strictly increasing -tuples of ordinals, write when, for every integer with $s+1\leq i\leq n_s-s-2,
These are coordinate inequalities supplied by the usual Specker disjoint types. The proof below uses the inequalities directly.
Lemma 3.1. Suppose that are strictly increasing -tuples of ordinals and, for every , either or . If is odd, then .
Proof. Suppose that . Choose one of the two available orientations for each step. Reversing the walk if necessary, arrange that the number of forward steps exceeds the number of reverse steps. This is possible because is odd. In particular, .
Start at index . At a forward step decrease the index by , and at a reverse step increase it by . Thus
At most changes occur, each of absolute value at most . Since , every index lies in
The corresponding inequality in (4) therefore applies at every step and gives
On the other hand,
As is increasing, , a contradiction.
For later use put
The th block of an increasing sequence is the tuple
The host graph
Vertex data
Let be the set of hereditarily countable sets. We use the von Neumann representation of ordinals and fix the Kuratowski encoding of ordered pairs. A vertex is a quadruple
with the following properties.
is transitive and , where is a nonzero limit ordinal.
is a function.
is strictly increasing and cofinal in .
Let be the set of all such vertices. Each vertex is identified with the code
where functions are represented by their graphs. This code is hereditarily countable, and distinct vertex data have distinct codes. We consequently regard as a subset of .
Every member of has countable rank. This follows by well-founded induction from
and the fact that a countable supremum of countable ordinals is countable. In particular, is a set, contained in the cumulative-hierarchy level . The coding also gives
For vertices , write when . Then
Edges and their layers
For and , a vertex is eligible at if
When an eligible vertex exists, choose one and denote it by . Put
and let . Formula (8) excludes loops and shows that rank is a proper coloring of . Hence
Lemma 4.1. For every , the graph is a forest. For every , the graph
has no odd closed walk of length at most .
Proof. A finite cycle in would have a vertex of maximum rank. Its two neighbors on the cycle have smaller rank, so each must be . This contradicts their distinctness. Thus is a forest and admits a proper binary coloring.
For the second assertion, map a vertex to the increasing tuple . An edge in has a label . Its two image tuples satisfy in one of the two orientations by (9). An odd closed walk of length at most would therefore contradict Lemma 3.1. The images of its vertices may repeat, which is allowed in that lemma. □
Choose a binary coloring of for each . For , let
Every edge whose endpoints have the same -value belongs to the tail . Lemma 4.1 implies that no odd closed walk of length at most is monochromatic under .
Countable closures and reflection
We prove that admits no coloring into . The countable closures below supply the reflection argument for the construction.
Lemma 5.1. Let be a set and let be a countable collection of functions, each of the form for some finite . Every countable subset of is contained in a countable subset closed under every member of .
Proof. Starting with the given countable set , let contain and all values of functions in on tuples from . Each is countable. The union is countable and closed, since every finite tuple from is contained in some . □
Fix an arbitrary function . The functions used for closure will depend on . For a finite sequence of countable ordinals and , define predicates recursively. The predicate means that some satisfies
For , let
Here and below the quantified ordinals are less than .
For every and finite , choose the following values, using zero as a default whenever the specified choice is unavailable.
If fails, choose a bound such that
Whenever a witness exists above , choose satisfying
If holds, choose a vertex witnessing it.
The vertex in the third item is represented by its code in .
These choices yield countably many finitary functions on . For precision, for each possible input length take the corresponding function, and decode an arbitrary input as the countable ordinal . For an ordinal input , this decoding returns . Ordinal outputs and vertex codes belong to .
Include also the following functions in the closure family. For each , fix a sequence whose range contains every member of and whose values lie in . Include all functions , the constant , and the function
with its ordinal value regarded as an element of .
Lemma 5.2. There are increasing countable subsets for , closed under all the chosen functions, such that, on writing
each is transitive, each is a nonzero countable limit ordinal, and
The union is closed and transitive, belongs to , and satisfies
Proof. Apply Lemma 5.1 to obtain containing . Closure under the functions makes transitive. Its ordinals form an initial segment of . Closure under makes that segment closed under successors, and it contains all finite ordinals. Since is countable, its ordinal part is a nonzero countable limit ordinal .
Having constructed , apply Lemma 5.1 to to obtain . The same argument gives transitivity and the required properties of its ordinal part. Inclusion of gives (14).
The union is countable and transitive. Every finite tuple from it lies in one stage, so it is closed under the chosen functions. A countable transitive set of hereditarily countable sets is hereditarily countable. Its ordinal part is the union of the , which is their supremum.
Define , and define on by
Uniqueness of the vertex code makes this definition unambiguous. Lemma 5.2 shows that
is a vertex of . Put .
Lemma 5.3. For every ,
holds. In particular, holds for every .
Proof. Induct on , simultaneously for all . For , the vertex witnesses (17).
Suppose the statement holds for , and put . The induction hypothesis at gives
If failed, the chosen bound would belong to . Indeed, every entry with belongs to by (14), and is closed under the bound function. As the bound is an ordinal, it is less than . Equation (13) would then exclude the displayed instance of , a contradiction. □
Lemma 5.4. Let , and let be a nondecreasing sequence of natural numbers. There is a vertex with such that, for every ,
Proof. Starting with , construct countable ordinals . At stage , retain
Set if , and otherwise. The ordinal belongs to . Every previously chosen belongs to . Closure under the witness function permits the choice
It satisfies and preserves the displayed predicate with in place of . Since is an ordinal in , it is less than .
At the end, holds. Closure of under the vertex-selection function gives a witnessing vertex . Its first ladder entries are the , so it satisfies (18). □
The chromatic number and the conclusion
Proposition 6.1. The graph has chromatic number .
Proof. The upper bound is (10). Suppose that is a proper coloring, and construct the sets , the vertex , and the color as above. Set . For and , prescribe
This sequence is nondecreasing within every block. Its values in the th block are at least and strictly less than , so it is nondecreasing across the blocks as well.
Apply Lemma 5.4 to obtain of color . Fix and . The upper inequality in (18) and (19) give
Apply the lower inequality in (18) at the coordinate . Its prescribed gap index is , so
Thus for every . Since and , the vertex is eligible at .
The chosen predecessor therefore exists. Its eligibility gives , and (15) gives . But , contradicting properness of . Hence has no countable coloring, and (10) yields . □
Proof of Theorem 1.1. Proposition 6.1 gives . The finite colorings in (11) satisfy the hypotheses of Proposition 2.1, so every with has . Such an cannot have chromatic number . This proves both assertions. □
Acknowledgment
The authors acknowledge assistance from OpenAI’s ChatGPT in the development and checking of the argument and in preparing the exposition.
References
- [1]N. G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A 54 = Indag. Math. 13 (1951), 369–373.
- [2]P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42. doi:10.1007/BF02579174.DOI
- [3]P. Komjáth and S. Shelah, Finite subgraphs of uncountably chromatic graphs, J. Graph Theory 49 (2005), no. 1, 28–38. doi:10.1002/jgt.20060.DOI
- [4]C. Lambie-Hanson, On the growth rate of chromatic numbers of finite subgraphs, Adv. Math. 369 (2020), article 107176. doi:10.1016/j.aim.2020.107176.
- [5]C. Lambie-Hanson, Finite subgraphs of uncountable graphs, CMU Mathematical Logic Seminar, April 28, 2020, seminar slides, 53–107.