gpt pro 5.2 attempt on Math-660, version 2

Erdős Problem #62 (Round 2): Common $4$-chromatic subgraphs of $\aleph_1$-chromatic graphs

1) ROUND-2 OBJECTIVE

Path (B): counterexample-driven gap-closure. Round 1 reduced the question to whether two $\aleph_1$-chromatic graphs must share some finite $4$-chromatic subgraph type, but left open how one could either force an intersection or construct two graphs with disjoint $4$-chromatic finite spectra.

In Round 2 I push the counterexample direction by sharpening the finite reduction (from "finite $4$-chromatic" to "finite $4$-critical"), and by proving that no fixed non-bipartite graph (hence no fixed $4$-chromatic graph) can be unavoidable in the class of uncountably chromatic graphs. This rules out an entire family of "single-template" proof strategies and isolates the precise combinatorial difficulty: simultaneous avoidance of unbounded-odd-girth $4$-critical graphs.

2) ROUND-1 FOUNDATION USED

I rely on the following Round 1 results (and do not re-prove them):

• Lemma 1 (compactness for finite $k$-colorability): if every finite induced subgraph of $G$ is $k$-colorable then $G$ is $k$-colorable.
• Lemma 2 (finite $(k+1)$-chromatic induced subgraph): if $\chi(G)>k$ then $G$ contains a finite induced subgraph $H$ with $\chi(H)=k+1$.
• Round 1 gap formulation: for $\chi(G_i)=\aleph_1$, the problem reduces to whether the sets of isomorphism types of finite $4$-chromatic graphs appearing in $G_1$ and $G_2$ must intersect.

3) NEW INSIGHT / TOOL (ROUND-2)

1. Critical reduction: it suffices to look for a finite $4$-vertex-critical common subgraph (a strictly smaller target family than all finite $4$-chromatic graphs).
2. Odd-girth avoidance principle: using the existence of uncountably chromatic graphs with arbitrarily large odd girth, any fixed non-bipartite graph $H$ (in particular any fixed $4$-chromatic $H$) can be avoided by some $\aleph_1$-chromatic graph.
3. Finite-family non-compactness: consequently, no finite list of $4$-chromatic graphs can serve as a universal "menu" from which every $\aleph_1$-chromatic graph must contain at least one.

4) ATTACK PLAN (ROUND-2)

• Gap after Round 1: Round 1 showed each $G_i$ contains some finite $4$-chromatic subgraph, but did not control which. The missing step is either:
  1. prove an intersection theorem forcing a shared finite $4$-chromatic type, or
  2. build two $\aleph_1$-chromatic graphs with disjoint finite $4$-chromatic spectra.
• Round 2 approach: I sharpen the reduction and then show that "single-template" and even "finite-template" strategies are doomed: for any predetermined (finite) candidate set, one can build an $\aleph_1$-chromatic graph avoiding all of them. This isolates that any counterexample (or any positive proof) must engage with infinitely many $4$-critical graphs of unbounded odd girth.

5) WORK (ROUND-2)

5.1. Reduction to finite $4$-critical graphs

Definition.

A finite graph $F$ is $4$-vertex-critical if $\chi(F)=4$ and for every vertex $v\in V(F)$ we have $\chi(F-v)\le 3$. (Equivalently: every proper induced subgraph of $F$ is $3$-colorable.)

Lemma 3 (every $\chi\ge 4$ graph contains a finite $4$-vertex-critical induced subgraph).

If $\chi(G)\ge 4$, then $G$ contains a finite induced subgraph $F$ that is $4$-vertex-critical.

Proof (using Round 1 Lemma 2). Apply Round 1 Lemma 2 with $k=3$ to obtain a finite induced subgraph $H\subseteq G$ with $\chi(H)=4$. Among all induced subgraphs of $H$ with chromatic number $4$, choose one $F$ with the minimum number of vertices. Then $\chi(F)=4$. If $F'$ is a proper induced subgraph of $F$, then by minimality $\chi(F')\le 3$. Thus $F$ is $4$-vertex-critical. $\square$

Corollary 4 (pairwise common $4$-chromatic $\Leftrightarrow$ common finite $4$-critical).

Let $G_1,G_2$ be graphs. The following are equivalent:

1. There exists a graph $H$ with $\chi(H)=4$ that is a subgraph of both $G_1$ and $G_2$.
2. There exists a finite $4$-vertex-critical graph $F$ that is a subgraph of both $G_1$ and $G_2$.

The same equivalence holds with "$\chi(H)=\aleph_0$" in place of "$\chi(H)=4$".

Proof. $2$$\Rightarrow$$1$ is trivial since $F$ itself has chromatic number $4$. For $1$$\Rightarrow$$2$, let $H$ be a common $4$-chromatic subgraph. By Lemma 3 applied to $H$, there is a finite induced subgraph $F\subseteq H$ that is $4$-vertex-critical. Since subgraph-containment is transitive, $F$ is a subgraph of both $G_1$ and $G_2$.

If $\chi(H)=\aleph_0$, then in particular $\chi(H)\ge 4$, so Lemma 3 again gives a finite $4$-vertex-critical induced subgraph $F\subseteq H$, hence common to $G_1,G_2$. $\square$

Consequence. Problem #62 is equivalent to:

Do any two graphs $G_1,G_2$ with $\chi(G_i)=\aleph_1$ necessarily contain a common finite $4$-vertex-critical subgraph?

This is a strictly sharper "finite target" than Round 1 (finite $4$-chromatic).

5.2. Odd-girth avoidance: no fixed $4$-chromatic template can be obligatory

Definition.

For a graph $G$, its odd girth $\mathrm{og}(G)$ is the minimum length of an odd cycle in $G$ if $G$ is non-bipartite, and $\infty$ if $G$ is bipartite.

External input (Erdős--Hajnal; Lovász).

For every integer $s\ge 3$ and every infinite cardinal $\kappa$, there exists a graph $G$ of cardinality $\kappa$ and chromatic number $\kappa$ containing no odd circuit of length $\le s$ (equivalently: $\mathrm{og}(G)>s$). This is stated in Hajnal--Komjáth $1984$ as known background, with pointer to Erdős--Hajnal $1966$ and Lovász $1969$ for constructive proofs.

Lemma 5 (avoidance of a fixed non-bipartite graph).

Let $H$ be any (finite or infinite) non-bipartite graph, and let $\kappa$ be any infinite cardinal. Then there exists a graph $G$ with $|V(G)|=\kappa$ and $\chi(G)=\kappa$ such that $H$ is not a subgraph of $G$. In particular, for $\kappa=\aleph_1$ there is an $\aleph_1$-chromatic graph omitting $H$.

Proof. Since $H$ is non-bipartite, it contains at least one odd cycle; thus $\mathrm{og}(H)=:t<\infty$. Apply the external input with parameter $s=t$ to obtain a graph $G$ of size and chromatic number $\kappa$ with odd girth $\mathrm{og}(G)>t$. If there were an embedding of $H$ into $G$, the image of an odd cycle of length $t$ in $H$ would be an odd cycle of length $t$ in $G$, contradicting $\mathrm{og}(G)>t$. Hence $H$ does not embed into $G$. $\square$

Corollary 6 (no universal $4$-chromatic graph).

There is no fixed graph $H$ with $\chi(H)\ge 3$ (in particular, $\chi(H)=4$ or $\chi(H)=\aleph_0$) that is a subgraph of every $\aleph_1$-chromatic graph.

Reason. Apply Lemma 5 with $\kappa=\aleph_1$. $\square$

Corollary 7 (finite-family non-compactness for $4$-chromatic candidates).

Let $\mathcal{H}$ be a finite set of graphs, each of chromatic number at least $3$. Then there exists an $\aleph_1$-chromatic graph $G$ that contains none of the graphs in $\mathcal{H}$ as subgraphs. In particular, for any finite list of finite $4$-chromatic graphs $H_1,\dots,H_m$, there is an $\aleph_1$-chromatic graph avoiding all of them.

Proof. Let $t:=\max\{\mathrm{og}(H):H\in\mathcal{H}\}$; this maximum is finite since $\mathcal{H}$ is finite and each $\mathrm{og}(H)<\infty$. Choose an $\aleph_1$-chromatic graph $G$ with odd girth $>t$. Then no $H\in\mathcal{H}$ embeds into $G$ by the same odd-cycle argument as in Lemma 5. $\square$

Interpretation for Problem #62. Any proof of a positive answer cannot proceed by:

• exhibiting a single $4$-chromatic "unavoidable" template, nor
• exhibiting a finite list of $4$-chromatic templates, one of which must appear in every $\aleph_1$-chromatic graph.

Both strategies are refuted by Corollary 6 and Corollary 7.

5.3. Baseline common-subgraph facts (chromatic $2$ and $3$)

These do not solve the $4$-chromatic question, but they calibrate what is already forced.

Known fact A (finite obligatory graphs are exactly finite bipartite graphs).

Hajnal--Komjáth $1984$ recalls that a graph of uncountable chromatic number must contain a $4$-cycle and in fact must contain every finite bipartite graph. Consequently any two $\aleph_1$-chromatic graphs share, for each fixed finite bipartite graph $B$, a common copy of $B$ (hence a common $2$-chromatic subgraph).

Known fact B (a specific countable bipartite graph is obligatory).

Hajnal--Komjáth (1984, Theorem 1) proves that every graph $G$ with $\chi(G)\ge\aleph_1$ contains a specific countable bipartite graph $F$ (the "semicomplete bipartite" graph). Hence any two $\aleph_1$-chromatic graphs have a common countable subgraph of chromatic number $2$.

Known fact C (common $3$-chromatic subgraph).

Erdős--Hajnal--Shelah (as also recorded in the problem statement) implies that any two $\aleph_1$-chromatic graphs have a common odd cycle $C_{2k+1}$ for some sufficiently large $k$, hence a common $3$-chromatic subgraph.

5.4. A precise reduction for a counterexample strategy

Let $\mathcal{C}_4$ denote the (countable) set of isomorphism types of finite $4$-vertex-critical graphs. For a graph $G$, let \[ \mathcal{C}_4(G):=\{F\in\mathcal{C}_4 : F\text{ embeds into }G\}. \] By Corollary 4, Problem #62 asks whether for all $\aleph_1$-chromatic $G_1,G_2$ we must have \[ \mathcal{C}_4(G_1)\cap\mathcal{C}_4(G_2)\ne\varnothing. \]

Proposition 8 (conditional counterexample reduction).

Assume the following

(*) For every subset $S\subseteq\mathcal{C}_4$ there exists a graph $G_S$ with $\chi(G_S)=\aleph_1$ such that $\mathcal{C}_4(G_S)\cap S=\varnothing$.

Then the answer to Problem #62 is negative.

Proof. Let $S\subseteq\mathcal{C}_4$ be arbitrary and put $T:=\mathcal{C}_4\setminus S$. Let $G_1:=G_S$ and $G_2:=G_T$ given by (*). Then $\mathcal{C}_4(G_1)\subseteq T$ and $\mathcal{C}_4(G_2)\subseteq S$, hence $\mathcal{C}_4(G_1)\cap\mathcal{C}_4(G_2)=\varnothing$. By Corollary 4, $G_1$ and $G_2$ have no common $4$-chromatic (nor $\aleph_0$-chromatic) subgraph. $\square$

What Round 2 adds: Proposition 8 formalizes the exact missing ingredient for a disproof: the ability to build $\aleph_1$-chromatic graphs simultaneously omitting arbitrary specified families of finite $4$-critical graphs. Corollary 7 shows this is possible for any finite family (indeed any family with bounded odd girth), but it remains open for families with unbounded odd girth, which is precisely where $4$-critical graphs naturally live.

6) ADVERSARIAL VERIFICATION

• Transitivity check (Corollary 4): If $F$ is an induced subgraph of $H$ and $H$ is a subgraph of $G_i$, then $F$ is a subgraph of $G_i$ (edges of $F$ are edges of $H$ and hence map to edges of $G_i$). No induced-ness is needed for this transitivity.

• Criticality definition: Lemma 3 produces a finite induced subgraph $F$ minimal among induced subgraphs of chromatic number $4$. This ensures vertex-criticality (every proper induced subgraph is $3$-colorable). No edge-critical property is claimed or used.

• Odd-girth argument (Lemma 5): Any non-bipartite graph contains a finite odd cycle, so $\mathrm{og}(H)$ is a finite odd integer. Embedding preserves cycles, so forbidding cycles up to that length suffices.

• External input scope: The avoidance Lemma 5 hinges on the existence of $\aleph_1$-chromatic graphs with arbitrarily large odd girth. If this external fact were weakened (e.g., only large girth but not odd girth), the avoidance implication would fail for graphs whose shortest odd cycle is small.

• No overreach: Proposition 8 is explicitly conditional; it does not assert (*) in ZFC. It only isolates (*) as a sufficient principle for a counterexample.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 advances beyond Round 1 by:

• reducing Problem #62 to the intersection problem for finite $4$-vertex-critical graphs (Corollary 4);
• proving that no fixed non-bipartite graph (hence no fixed $4$-chromatic or $\aleph_0$-chromatic graph) can be obligatory for $\aleph_1$-chromatic graphs (Lemma 5 and Corollary 6);
• showing a non-compactness barrier: any finite list of $4$-chromatic candidates can be simultaneously avoided by some $\aleph_1$-chromatic graph (Corollary 7);
• isolating a concrete sufficient condition (*) that would yield a counterexample pair (Proposition 8).

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 40%

9) REFERENCES

• A. Hajnal, P. Komjáth, What must and what need not be contained in a graph of uncountable chromatic number?, Combinatorica 4$1$ $1984$, 47--52. (Used for: existence of uncountably chromatic graphs with large odd girth; obligatory finite bipartite subgraphs; and the obligatory countable bipartite graph $F$.)
• P. Erdős, A. Hajnal, S. Shelah, On some general properties of chromatic numbers, Topics in topology (Proc. Colloq., Keszthely, 1972), 243--255 $1974$. (Used only as recorded in the problem statement for the common $3$-chromatic/odd-cycle phenomenon.)