betaFeedback

WorksMathematics

A ZFC counterexample to Taylor's conjecture on finite subgraphs

Abstract

We construct, in ZFC, a graph GG of chromatic number ℵ1\aleph_1 such that every graph whose finite ordinary subgraphs embed into GG has chromatic number at most 2ℵ02^{\aleph_0}. Taking the target chromatic number to be (2ℵ0)+(2^{\aleph_0})^+ 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 GG.

Introduction

All graphs in this paper are simple and undirected. An embedding of a graph FF into a graph GG is an injective map on vertices that preserves adjacency. Write Age⁡(G)\operatorname{Age}(G) for the class of finite graphs that embed into GG, up to isomorphism. The chromatic number χ(G)\chi(G) is the least cardinality of a set admitting a proper coloring of GG.

A conjecture of Walter Taylor, recorded by [2], asks whether every graph GG with χ(G)=ℵ1\chi(G)=\aleph_1 has the following property. For every cardinal κ\kappa, there is a graph HH with

χ(H)=κandAge⁡(H)⊆Age⁡(G).(1)\chi(H)=\kappa\qquad\text{and} \qquad\operatorname{Age}(H)\subseteq\operatorname{Age}(G). \tag*{(1)}

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 c=2ℵ0\mathfrak{c}=2^{\aleph_0}.

Theorem 1.1. There is a graph GG with χ(G)=ℵ1\chi(G)=\aleph_1 such that, for every graph HH,

Age⁡(H)⊆Age⁡(G)⇒χ(H)≤c.(2)\operatorname{Age}(H)\subseteq\operatorname{Age}(G)\quad\Rightarrow\quad\chi(H)\leq\mathfrak{c}. \tag*{(2)}

Consequently, (1.1) fails for this GG and κ=c+\kappa=\mathfrak{c}^+.

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 N={0,1,2,…}\mathbb{N}=\{0,1,2,\ldots\}. A closed walk of length ℓ\ell is a sequence v0,v1,…,vℓ=v0v_0,v_1,\ldots,v_\ell=v_0 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 j∈Nj\in\mathbb{N}, a graph GG admits a coloring aja_j into a finite nonempty set AjA_j such that no odd closed walk of length at most 2j+32j+3 is monochromatic under aja_j. If Age⁡(H)⊆Age⁡(G)\operatorname{Age}(H)\subseteq\operatorname{Age}(G), then χ(H)≤c\chi(H)\leq\mathfrak{c}.

Proof. Fix jj. Give AjA_j the discrete topology and consider the compact space

Xj=AjV(H).X_j = A_j^{V(H)}.

For every odd closed walk QQ of HH of length at most 2j+32j+3, let UQU_Q be the set of colorings in XjX_j that make QQ nonmonochromatic. Each UQU_Q is clopen because membership depends on finitely many coordinates.

A finite collection of these conditions involves a finite set S⊆V(H)S \subseteq V(H). The finite graph H[S]H[S] embeds into GG. Pulling back aja_j along such an embedding colors SS 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 HH. Thus the sets UQU_Q have the finite intersection property. Compactness gives a coloring

bj:V(H)⟶Ajb_j: V(H) \longrightarrow A_j

for which no odd closed walk of length at most 2j+32j+3 is monochromatic. This is the usual finite-color compactness principle underlying the de Bruijn–Erdős theorem [1].

Choose such a bjb_j for every jj and set

b(v)=⟨bj(v):j∈N⟩.b(v) = \langle b_j(v) : j \in\mathbb{N}\rangle.

Every fiber of bb induces a graph with no odd closed walk. Otherwise a walk of odd length ℓ\ell in a fiber would be monochromatic under bjb_j for any jj with ℓ≤2j+3\ell\le2j+3.

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 bb, and denote the resulting bit at vv by ε(v)\varepsilon(v).

The map v↦(b(v),ε(v))v \mapsto(b(v),\varepsilon(v)) is a proper coloring of HH. Its color set has cardinality at most c\mathfrak{c}. In fact, each finite AjA_j embeds into N\mathbb{N}, so

∣(∏j∈NAj)×{0,1}∣≤∣NN×{0,1}∣=c.\left|\left(\prod_{j\in\mathbb{N}} A_j\right)\times\{0,1\}\right| \leq\left|\mathbb{N}^{\mathbb{N}}\times\{0,1\}\right|=\mathfrak{c}.

A finite coordinate obstruction

For a positive integer ss, define

Bs=(2s+1)(s+1),ns=2Bs+2s+3=4(s+1)2+1.(3)B_s=(2s+1)(s+1), \qquad n_s=2B_s+2s+3=4(s+1)^2+1. \tag*{(3)}

If aa and bb are strictly increasing nsn_s-tuples of ordinals, write a Rs ba\,R_s\,b when, for every integer ii with $s+1\leq i\leq n_s-s-2,

a(i)<b(i−s)andb(i)<a(i+s+1).(4)a(i)<b(i-s) \qquad\text{and}\qquad b(i)<a(i+s+1). \tag*{(4)}

These are coordinate inequalities supplied by the usual Specker disjoint types. The proof below uses the inequalities directly.

Lemma 3.1. Suppose that a0,a1,…,aℓ=a0a_0,a_1,\ldots,a_\ell=a_0 are strictly increasing nsn_s-tuples of ordinals and, for every t<ℓt<\ell, either at Rs at+1a_t\,R_s\,a_{t+1} or at+1 Rs ata_{t+1}\,R_s\,a_t. If ℓ\ell is odd, then ℓ>2s+1\ell>2s+1.

Proof. Suppose that ℓ≤2s+1\ell\leq2s+1. Choose one of the two available orientations for each step. Reversing the walk if necessary, arrange that the number uu of forward steps exceeds the number dd of reverse steps. This is possible because u+d=ℓu+d=\ell is odd. In particular, d≤sd\leq s.

Start at index i0=Bs+s+1i_0 = B_s + s + 1. At a forward step decrease the index by ss, and at a reverse step increase it by s+1s + 1. Thus

it+1={it−s,at Rs at+1 is the chosen orientation,it+s+1,at+1 Rs at is the chosen orientation.i_{t+1} = \begin{cases} i_t - s, & \text{at } R_s\ a_{t+1}\text{ is the chosen orientation},\\ i_t + s + 1, & a_{t+1}\ R_s\ a_t\text{ is the chosen orientation}. \end{cases}

At most ℓ\ell changes occur, each of absolute value at most s+1s + 1. Since ℓ(s+1)≤Bs\ell(s + 1) \le B_s, every index lies in

[s+1,2Bs+s+1]=[s+1,ns−s−2].[s + 1, 2B_s + s + 1] = [s + 1, n_s - s - 2].

The corresponding inequality in (4) therefore applies at every step and gives

a0(i0)<a1(i1)<⋯<aℓ(iℓ).a_0(i_0) < a_1(i_1) < \cdots< a_\ell(i_\ell).

On the other hand,

iℓ−i0=−su+(s+1)d=−s(u−d)+d≤−s+d≤0.i_\ell- i_0 = -su + (s + 1)d = -s(u - d) + d \le-s + d \le0.

As aℓ=a0a_\ell= a_0 is increasing, aℓ(iℓ)≤a0(i0)a_\ell(i_\ell) \le a_0(i_0), a contradiction. □\square

For later use put

sj=j+1,nj=nsj,b0=0,bj+1=bj+nj.(5)s_j = j + 1,\qquad n_j = n_{s_j},\qquad b_0 = 0,\qquad b_{j+1} = b_j + n_j. \tag*{(5)}

The jjth block of an increasing sequence C:N→ω1C:\mathbb{N} \to\omega_1 is the tuple

C[j]=⟨C(bj+i):0≤i<nj⟩.C[j] = \langle C(b_j + i) : 0 \le i < n_j\rangle.

The host graph

Vertex data

Let H=H(ℵ1)\mathcal{H} = H(\aleph_1) 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

v=⟨Mv,δv,hv,Cv⟩(6)v = \langle M_v, \delta_v, h_v, C_v\rangle \tag*{(6)}

with the following properties.

  1. Mv∈HM_v \in\mathcal{H} is transitive and Mv∩ω1=δvM_v \cap\omega_1 = \delta_v, where δv\delta_v is a nonzero limit ordinal.

  2. hv:Mv→Nh_v:M_v \to\mathbb{N} is a function.

  3. Cv:N→δvC_v:\mathbb{N} \to\delta_v is strictly increasing and cofinal in δv\delta_v.

Let VV be the set of all such vertices. Each vertex is identified with the code

⟨Mv,⟨δv,⟨hv,Cv⟩⟩⟩,\langle M_v,\langle\delta_v,\langle h_v,C_v\rangle\rangle\rangle,

where functions are represented by their graphs. This code is hereditarily countable, and distinct vertex data have distinct codes. We consequently regard VV as a subset of H\mathcal{H}.

Every member of H\mathcal{H} has countable rank. This follows by well-founded induction from

rk⁡(x)=sup⁡{rk⁡(y)+1:y∈x}\operatorname{rk}(x) = \sup\{\operatorname{rk}(y) + 1 : y \in x\}

and the fact that a countable supremum of countable ordinals is countable. In particular, H\mathcal{H} is a set, contained in the cumulative-hierarchy level Vω1V_{\omega_1}. The coding also gives

rk⁡(Mv)<rk⁡(v)<ω1.(7)\operatorname{rk}(M_v) < \operatorname{rk}(v) < \omega_1. \tag*{(7)}

For vertices u,vu,v, write u≺vu \prec v when u∈Mvu \in M_v. Then

u≺v⟹rk⁡(u)<rk⁡(Mv)<rk⁡(v).(8)u \prec v \mathrel{\Longrightarrow} \operatorname{rk}(u) < \operatorname{rk}(M_v) < \operatorname{rk}(v). \tag*{(8)}

Edges and their layers

For v∈Vv \in V and k∈Nk \in\mathbb{N}, a vertex uu is eligible at (v,k)(v,k) if

u∈Mv,hv(u)=k,Cu[j] Rsj Cv[j](0≤j≤k).(9)u \in M_v,\qquad h_v(u)=k,\qquad C_u[j]\ R_{s_j}\ C_v[j]\quad(0 \le j \le k). \tag*{(9)}

When an eligible vertex exists, choose one and denote it by pk(v)p_k(v). Put

Ek={{v,pk(v)}:v∈V and pk(v) is defined},E=⋃k∈NEk,E_k=\{\{v,p_k(v)\}:v\in V\text{ and }p_k(v)\text{ is defined}\},\qquad E=\bigcup_{k\in\mathbb{N}}E_k,

and let G=(V,E)G=(V,E). Formula (8) excludes loops and shows that rank is a proper coloring of GG. Hence

χ(G)≤ℵ1.(10)\chi(G)\le\aleph_1. \tag*{(10)}

Lemma 4.1. For every kk, the graph (V,Ek)(V,E_k) is a forest. For every jj, the graph

G≥j=(V,⋃k≥jEk)G_{\ge j}=\left(V,\bigcup_{k\ge j}E_k\right)

has no odd closed walk of length at most 2j+32j+3.

Proof. A finite cycle in (V,Ek)(V,E_k) would have a vertex vv of maximum rank. Its two neighbors on the cycle have smaller rank, so each must be pk(v)p_k(v). This contradicts their distinctness. Thus (V,Ek)(V,E_k) is a forest and admits a proper binary coloring.

For the second assertion, map a vertex vv to the increasing tuple Cv[j]C_v[j]. An edge in G≥jG_{\ge j} has a label k≥jk\ge j. Its two image tuples satisfy RsjR_{s_j} in one of the two orientations by (9). An odd closed walk of length at most 2j+3=2sj+12j+3=2s_j+1 would therefore contradict Lemma 3.1. The images of its vertices may repeat, which is allowed in that lemma. □

Choose a binary coloring ckc_k of (V,Ek)(V,E_k) for each kk. For j∈Nj\in\mathbb{N}, let

aj(v)=⟨c0(v),…,cj−1(v)⟩∈{0,1}j.(11)a_j(v)=\langle c_0(v),\ldots,c_{j-1}(v)\rangle\in\{0,1\}^j. \tag*{(11)}

Every edge whose endpoints have the same aja_j-value belongs to the tail G≥jG_{\ge j}. Lemma 4.1 implies that no odd closed walk of length at most 2j+32j+3 is monochromatic under aja_j.

Countable closures and reflection

We prove that GG admits no coloring into N\mathbb{N}. The countable closures below supply the reflection argument for the construction.

Lemma 5.1. Let XX be a set and let F\mathcal{F} be a countable collection of functions, each of the form Xr→XX^r\to X for some finite rr. Every countable subset of XX is contained in a countable subset closed under every member of F\mathcal{F}.

Proof. Starting with the given countable set A0A_0, let Am+1A_{m+1} contain AmA_m and all values of functions in F\mathcal{F} on tuples from AmA_m. Each AmA_m is countable. The union A=⋃m<ωAmA=\bigcup_{m<\omega}A_m is countable and closed, since every finite tuple from AA is contained in some AmA_m. □

Fix an arbitrary function f:V→Nf:V\to\mathbb{N}. The functions used for closure will depend on ff. For a finite sequence αˉ\bar{\alpha} of countable ordinals and k,r∈Nk,r\in\mathbb{N}, define predicates Prk(αˉ)P^k_r(\bar{\alpha}) recursively. The predicate P0k(αˉ)P^k_0(\bar{\alpha}) means that some v∈Vv\in V satisfies

f(v)=kandCv(i)=αi(i<∣αˉ∣).f(v)=k\qquad\text{and}\qquad C_v(i)=\alpha_i\quad(i<|\bar{\alpha}|).

For r≥0r\ge0, let

Pr+1k(αˉ)⟺∀β<ω1 ∃γ>β Prk(αˉ⌢⟨γ⟩).(12)P^k_{r+1}(\bar{\alpha})\Longleftrightarrow\forall\beta<\omega_1\ \exists\gamma>\beta\ P^k_r(\bar{\alpha}^{\frown}\langle\gamma\rangle). \tag*{(12)}

Here and below the quantified ordinals are less than ω1\omega_1.

For every k,rk,r and finite αˉ\bar{\alpha}, choose the following values, using zero as a default whenever the specified choice is unavailable.

  1. If Pr+1k(αˉ)P^{k}_{r+1}(\bar{\alpha}) fails, choose a bound Bk,r(αˉ)<ω1B_{k,r}(\bar{\alpha}) < \omega_1 such that

γ>Bk,r(αˉ)⟹¬Prk(αˉ⌢⟨γ⟩).(13)\gamma> B_{k,r}(\bar{\alpha}) \quad\Longrightarrow\quad\neg P^{k}_{r}(\bar{\alpha}\mathbin{\frown}\langle\gamma\rangle). \tag*{(13)}
  1. Whenever a witness exists above β\beta, choose Wk,r(αˉ,β)>βW_{k,r}(\bar{\alpha},\beta) > \beta satisfying

Prk(αˉ⌢⟨Wk,r(αˉ,β)⟩).P^{k}_{r}(\bar{\alpha}\mathbin{\frown}\langle W_{k,r}(\bar{\alpha},\beta)\rangle).
  1. If P0k(αˉ)P^{k}_{0}(\bar{\alpha}) holds, choose a vertex Sk(αˉ)S_k(\bar{\alpha}) witnessing it.

The vertex in the third item is represented by its code in H\mathcal{H}.

These choices yield countably many finitary functions on H\mathcal{H}. For precision, for each possible input length take the corresponding function, and decode an arbitrary input x∈Hx \in\mathcal{H} as the countable ordinal rk⁡(x)\operatorname{rk}(x). For an ordinal input α\alpha, this decoding returns α\alpha. Ordinal outputs and vertex codes belong to H\mathcal{H}.

Include also the following functions in the closure family. For each x∈Hx \in\mathcal{H}, fix a sequence en(x)e_n(x) whose range contains every member of xx and whose values lie in x∪{∅}x \cup\{\varnothing\}. Include all functions ene_n, the constant ∅\varnothing, and the function

x⟼rk⁡(x)+1,x \longmapsto\operatorname{rk}(x)+1,

with its ordinal value regarded as an element of H\mathcal{H}.

Lemma 5.2. There are increasing countable subsets Mi⊆HM_i \subseteq\mathcal{H} for i<ωi < \omega, closed under all the chosen functions, such that, on writing

δi=Mi∩ω1,\delta_i=M_i\cap\omega_1,

each MiM_i is transitive, each δi\delta_i is a nonzero countable limit ordinal, and

δi∈Mi+1,δi<δi+1.(14)\delta_i\in M_{i+1},\qquad\delta_i<\delta_{i+1}. \tag*{(14)}

The union M∞=⋃iMiM_\infty=\bigcup_i M_i is closed and transitive, belongs to H\mathcal{H}, and satisfies

M∞∩ω1=δ∞=sup⁡iδi.M_\infty\cap\omega_1=\delta_\infty=\sup_i\delta_i.

Proof. Apply Lemma 5.1 to obtain M0M_0 containing ∅\varnothing. Closure under the functions ene_n makes M0M_0 transitive. Its ordinals form an initial segment of ω1\omega_1. Closure under x⟼rk⁡(x)+1x\longmapsto\operatorname{rk}(x)+1 makes that segment closed under successors, and it contains all finite ordinals. Since M0M_0 is countable, its ordinal part is a nonzero countable limit ordinal δ0\delta_0.

Having constructed MiM_i, apply Lemma 5.1 to Mi∪{δi}M_i\cup\{\delta_i\} to obtain Mi+1M_{i+1}. The same argument gives transitivity and the required properties of its ordinal part. Inclusion of δi\delta_i 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 δi\delta_i, which is their supremum. □\square

Define Cτ(i)=δiC_\tau(i)=\delta_i, and define hτh_\tau on M∞M_\infty by

hτ(x)={f(v),x is the code of a vertex v∈V,0,otherwise.(15)h_\tau(x)= \begin{cases} f(v), & x\text{ is the code of a vertex }v\in V,\\ 0, & \text{otherwise}. \end{cases} \tag*{(15)}

Uniqueness of the vertex code makes this definition unambiguous. Lemma 5.2 shows that

τ=⟨M∞,δ∞,hτ,Cτ⟩(16)\tau=\langle M_\infty,\delta_\infty,h_\tau,C_\tau\rangle \tag*{(16)}

is a vertex of GG. Put k=f(τ)k=f(\tau).

Lemma 5.3. For every r,i∈Nr,i\in\mathbb{N},

Prk(⟨δ0,…,δi−1⟩)(17)P^{k}_{r}(\langle\delta_0,\ldots,\delta_{i-1}\rangle) \tag*{(17)}

holds. In particular, Prk(∅)P^{k}_{r}(\varnothing) holds for every rr.

Proof. Induct on rr, simultaneously for all ii. For r=0r=0, the vertex τ\tau witnesses (17).

Suppose the statement holds for rr, and put δˉi=⟨δ0,…,δi−1⟩\bar{\delta}_i=\langle\delta_0,\ldots,\delta_{i-1}\rangle. The induction hypothesis at i+1i+1 gives

Prk(δˉi⌢⟨δi⟩).P^{k}_{r}(\bar{\delta}_i \frown\langle\delta_i\rangle).

If Pr+1k(δˉi)P^{k}_{r+1}(\bar{\delta}_i) failed, the chosen bound Bk,r(δˉi)B_{k,r}(\bar{\delta}_i) would belong to MiM_i. Indeed, every entry δj\delta_j with j<ij<i belongs to MiM_i by (14), and MiM_i is closed under the bound function. As the bound is an ordinal, it is less than δi\delta_i. Equation (13) would then exclude the displayed instance of PrkP^k_r, a contradiction. □

Lemma 5.4. Let N∈NN\in\mathbb{N}, and let (gt)t<N(g_t)_{t<N} be a nondecreasing sequence of natural numbers. There is a vertex v∈M∞∩Vv\in M_\infty\cap V with f(v)=kf(v)=k such that, for every t<Nt<N,

Cv(t)<δgt,gt>0⇒δgt−1<Cv(t).(18)C_v(t)<\delta_{g_t},\qquad g_t>0\Rightarrow\delta_{g_t-1}<C_v(t). \tag*{(18)}

Proof. Starting with PNk(∅)P^k_N(\varnothing), construct countable ordinals γ0,…,γN−1\gamma_0,\ldots,\gamma_{N-1}. At stage tt, retain

PN−t−1k(⟨γ0,…,γt−1⟩).P^k_{N-t-1}(\langle\gamma_0,\ldots,\gamma_{t-1}\rangle).

Set βt=0\beta_t=0 if gt=0g_t=0, and βt=δgt−1\beta_t=\delta_{g_t-1} otherwise. The ordinal βt\beta_t belongs to MgtM_{g_t}. Every previously chosen γj\gamma_j belongs to Mgj⊆MgtM_{g_j}\subseteq M_{g_t}. Closure under the witness function permits the choice

γt=Wk,N−t−1(⟨γ0,…,γt−1⟩,βt)∈Mgt.\gamma_t=W_{k,N-t-1}(\langle\gamma_0,\ldots,\gamma_{t-1}\rangle,\beta_t)\in M_{g_t}.

It satisfies γt>βt\gamma_t>\beta_t and preserves the displayed predicate with t+1t+1 in place of tt. Since γt\gamma_t is an ordinal in MgtM_{g_t}, it is less than δgt\delta_{g_t}.

At the end, P0k(⟨γ0,…,γN−1⟩)P^k_0(\langle\gamma_0,\ldots,\gamma_{N-1}\rangle) holds. Closure of M∞M_\infty under the vertex-selection function gives a witnessing vertex v∈M∞v\in M_\infty. Its first NN ladder entries are the γt\gamma_t, so it satisfies (18). □

The chromatic number and the conclusion

Proposition 6.1. The graph GG has chromatic number ℵ1\aleph_1.

Proof. The upper bound is (10). Suppose that f:V→Nf:V\to\mathbb{N} is a proper coloring, and construct the sets MiM_i, the vertex τ\tau, and the color k=f(τ)k=f(\tau) as above. Set N=bk+1N=b_{k+1}. For 0≤j≤k0\leq j\leq k and 0≤i<nj0\leq i<n_j, prescribe

gbj+i=bj+max⁡{i−sj,0}.(19)g_{b_j+i}=b_j+\max\{i-s_j,0\}. \tag*{(19)}

This sequence is nondecreasing within every block. Its values in the jjth block are at least bjb_j and strictly less than bj+1b_{j+1}, so it is nondecreasing across the blocks as well.

Apply Lemma 5.4 to obtain v∈M∞∩Vv\in M_\infty\cap V of color kk. Fix j≤kj\leq k and sj+1≤i≤nj−sj−2s_j+1\leq i\leq n_j-s_j-2. The upper inequality in (18) and (19) give

Cv(bj+i)<δbj+i−sj=Cτ(bj+i−sj).C_v(b_j+i)<\delta_{b_j+i-s_j}=C_\tau(b_j+i-s_j).

Apply the lower inequality in (18) at the coordinate bj+i+sj+1b_j+i+s_j+1. Its prescribed gap index is bj+i+1>0b_j+i+1>0, so

Cτ(bj+i)=δbj+i<Cv(bj+i+sj+1).C_\tau(b_j+i)=\delta_{b_j+i}<C_v(b_j+i+s_j+1).

Thus Cv[j]RsjCτ[j]C_v[j]\mathrel{R_{s_j}}C_\tau[j] for every j≤kj\leq k. Since v∈M∞=Mτv\in M_\infty=M_\tau and hτ(v)=f(v)=kh_\tau(v)=f(v)=k, the vertex vv is eligible at (τ,k)(\tau,k).

The chosen predecessor u=pk(τ)u=p_k(\tau) therefore exists. Its eligibility gives hτ(u)=kh_\tau(u)=k, and (15) gives f(u)=k=f(τ)f(u)=k=f(\tau). But {u,τ}∈Ek\{u,\tau\}\in E_k, contradicting properness of ff. Hence GG has no countable coloring, and (10) yields χ(G)=ℵ1\chi(G)=\aleph_1. □

Proof of Theorem 1.1. Proposition 6.1 gives χ(G)=ℵ1\chi(G)=\aleph_1. The finite colorings in (11) satisfy the hypotheses of Proposition 2.1, so every HH with Age⁡(H)⊆Age⁡(G)\operatorname{Age}(H)\subseteq\operatorname{Age}(G) has χ(H)≤c\chi(H)\leq\mathfrak{c}. Such an HH cannot have chromatic number c+\mathfrak{c}^{+}. 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. [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. [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. [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. [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. [5]C. Lambie-Hanson, Finite subgraphs of uncountable graphs, CMU Mathematical Logic Seminar, April 28, 2020, seminar slides, 53–107.

Paper details

vlnc:W_xpx3zn9u
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…
Contents