we-solve (beta)

Math-660-A3 · revision r1 · on Math-660

gpt pro 5.2 attempt on Math-660

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. FORMAL RESTATEMENT
  2. QUICK LITERATURE/CONTEXT CHECK
  3. ATTACK PLAN
  4. WORK
  5. VERIFICATION
  6. FINAL

If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$) which is a subgraph of both $G_1$ and $G_2$? Erdős also asked [Er87] about finding a common subgraph $H$ (with chromatic number either $4$ or $\aleph_0$) in any finite collection of graphs with chromatic number $\aleph_1$. Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594] . This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős wrote [Er87] that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth. References [EHS74] Erdős, P. and Hajnal, A. and Shelah, S., On some general properties of chromatic numbers . Topics in topology (Proc. Colloq., Keszthely, 1972) $1974$, 243-255. [Er87] Erdős, P., Some problems on finite and infinite graphs . Logic and combinatorics (Arcata, Calif., 1985) $1987$, 223-228.

FORMAL RESTATEMENT

A (simple) graph $G$ has chromatic number $\chi(G)$ equal to the least cardinal $\kappa$ such that $V(G)$ can be properly colored with $\kappa$ colors.

Given graphs $G_1,G_2$ with $\chi(G_1)=\chi(G_2)=\aleph_1$, question: must there exist a graph $H$ with $\chi(H)=4$ (or alternatively with $\chi(H)=\aleph_0$) such that $H$ is a subgraph of both $G_1$ and $G_2$? Here "$H$ is a subgraph of $G_i$" means there exists an injective map $f_i:V(H)\to V(G_i)$ such that if $xy\in E(H)$ then $f_i(x)f_i(y)\in E(G_i)$.

QUICK LITERATURE/CONTEXT CHECK

Only what is explicitly stated in the problem statement is used:
  • Erdős asked about common subgraphs of chromatic number $4$ or $\aleph_0$ in two (or finitely many) graphs of chromatic number $\aleph_1$.
  • The statement records (as known) that every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (chromatic number $3$), attributed to Erdős--Hajnal--Shelah.
  • Erdős suggested that probably every $\aleph_1$-chromatic graph contains all $4$-chromatic graphs of sufficiently large girth.
No other external results are assumed.

ATTACK PLAN

  • Prove basic structural facts that follow formally from $\chi(G)=\aleph_1$ (e.g., existence of finite $k$-chromatic subgraphs for every $k$).
  • Try to see whether those facts can force a common $4$-chromatic subgraph of two such graphs.
  • Since the main problem is infinite/set-theoretic, computation is not expected to decide it, but we do sanity checks on the finite-compactness statements used.

WORK

Lemma 1 (Compactness for $k$-colorability). Let $G$ be a (possibly infinite) graph and let $k\in\mathbb{N}$. If every finite induced subgraph of $G$ is $k$-colorable, then $G$ is $k$-colorable.

Proof. Let $V=V(G)$. Consider the set $\Omega:=\{1,2,\dots,k\}^V$ of all functions $f:V\to\{1,\dots,k\}$, equipped with the product topology where each factor $\{1,\dots,k\}$ is discrete (and hence compact). By Tychonoff's theorem, $\Omega$ is compact.

For each edge $uv\in E(G)$, define the closed set \[ A_{uv}:=\{f\in\Omega: f(u)\ne f(v)\}. \] This set is closed because its complement $\{f: f(u)=f(v)\}$ depends only on the coordinates $u,v$ and is clopen in the product topology. A proper $k$-coloring of $G$ is exactly a function $f\in\bigcap_{uv\in E(G)} A_{uv}$.

We show the family $\{A_{uv}:uv\in E(G)\}$ has the finite intersection property. Take any finite set of edges $F\subseteq E(G)$. Let $W$ be the (finite) set of vertices incident to edges in $F$. The induced subgraph $G[W]$ is finite, hence $k$-colorable by hypothesis; let $g:W\to\{1,\dots,k\}$ be a proper coloring. Extend $g$ arbitrarily to a function $f:V\to\{1,\dots,k\}$ (e.g., assign color $1$ to vertices in $V\setminus W$). Then $f\in\bigcap_{uv\in F}A_{uv}$. So every finite subcollection intersects.

By compactness of $\Omega$, the full intersection $\bigcap_{uv\in E(G)}A_{uv}$ is nonempty. Any $f$ in this intersection is a proper $k$-coloring of $G$. $\square$

Lemma 2 (Finite $k$-chromatic subgraphs exist at all finite levels). If $\chi(G)>k$ for some finite $k$, then $G$ contains a finite induced subgraph $H$ with $\chi(H)=k+1$. In particular, if $\chi(G)=\aleph_1$, then for every $t\in\mathbb{N}$ there exists a finite induced subgraph of $G$ with chromatic number exactly $t$.

Proof. Assume $\chi(G)>k$; equivalently, $G$ is not $k$-colorable. By Lemma 1 (contrapositive), there must exist a finite induced subgraph $H\subseteq G$ that is not $k$-colorable. Among all such $H$, choose one with the minimum number of vertices. Then every proper induced subgraph of $H$ is $k$-colorable (by minimality), but $H$ itself is not. Therefore $\chi(H)=k+1$.

If $\chi(G)=\aleph_1$, then $\chi(G)>t-1$ for every finite $t$, so applying the above with $k=t-1$ yields a finite induced subgraph with chromatic number exactly $t$. $\square$

Consequence for the main question. Given $G_1,G_2$ with $\chi(G_1)=\chi(G_2)=\aleph_1$, Lemma 2 implies:

  • $G_1$ contains some finite $4$-chromatic subgraph $H_1$,
  • $G_2$ contains some finite $4$-chromatic subgraph $H_2$.
However, this does not force $H_1\cong H_2$, and the problem asks whether there exists some $4$-chromatic graph $H$ that appears in both.

FAST REALITY CHECK. This problem is inherently about infinite graphs and uncountable chromatic number. Computation is not directly relevant to the main existence question. The only computationally-checkable component here is Lemma 2's finite-minimality argument; it is purely finite and self-contained.

VERIFICATION

  • Lemma 1 uses Tychonoff compactness; the construction of the closed sets $A_{uv}$ and the finite intersection property is explicit.
  • Lemma 2's minimization is over finite induced subgraphs and therefore well-founded.
  • Quantifiers: Lemma 2 produces a finite induced subgraph of chromatic number $k+1$ when $\chi(G)>k$; no set-theoretic assumptions beyond those used for Lemma 1 are hidden.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: if $\chi(G)=\aleph_1$, then for every finite $t$ the graph $G$ contains a finite induced subgraph of chromatic number exactly $t$ (Lemma 2). In particular, each $G_i$ contains some finite $4$-chromatic subgraph.

(ii) First gap: given two graphs $G_1,G_2$ with $\chi(G_i)=\aleph_1$, prove (or refute) that the sets \[ \mathcal{F}_i:=\{\text{isomorphism types of finite $4$-chromatic graphs that occur as subgraphs of }G_i\} \] have nonempty intersection.

(iii) Top 3 next moves:

  • Attempt a construction track: try to build two $\aleph_1$-chromatic graphs whose families $\mathcal{F}_1$ and $\mathcal{F}_2$ are disjoint by systematically forbidding a partition of the countably many finite $4$-chromatic graphs.
  • Attempt a forcing/unavoidability track: identify a specific finite $4$-chromatic "template" that might be unavoidable in every $\aleph_1$-chromatic graph (analogous to unavoidable odd cycles in the cited result).
  • Use girth considerations suggested in the statement: investigate whether large-girth $4$-chromatic graphs are forced as subgraphs in all $\aleph_1$-chromatic graphs and whether such forcing could be made uniform across two graphs.

(iv) Minimal counterexample structure (if the statement were false): two graphs $G_1,G_2$ with chromatic number $\aleph_1$ such that every graph that embeds into both has chromatic number at most $3$ (or at most finite), i.e., their common subgraph spectrum avoids all $4$-chromatic graphs.