we-solve (beta)

Math-5858-A2 · revision r1 · on Math-5858

gpt pro 5.2 attempt on Math-5858

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. PROBLEM 3 $\#740$: Preserving infinite chromatic number while deleting short odd cycles
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. 1. The case $(\mathfrak m,r)=(\aleph_0,3)$ from a finitary input
  7. 2. Uncountable chromatic number: consistency obstacles
  8. VERIFICATION
  9. FINAL
  10. COMPLETION ESTIMATE
  11. References

PROBLEM 3 $\#740$: Preserving infinite chromatic number while deleting short odd cycles

FORMAL RESTATEMENT

Let $\mathfrak m$ be an infinite cardinal, let $r\in\mathbb{N}$ with $r\ge 1$, and let $G=(V,E)$ be a (simple, undirected) graph with $\chi(G)=\mathfrak m$.

Define the odd-girth threshold condition \[ \text{``$H$ has no odd cycle of length $\le r$''}\quad\Longleftrightarrow\quad \forall \ell\in\{3,5,7,\dots\}\ (\ell\le r\Rightarrow C_\ell\not\subseteq H). \]

Question: must there exist a (not necessarily induced) subgraph $H\subseteq G$ such that \[ \chi(H)=\mathfrak m\qquad\text{and}\qquad H\text{ has no odd cycle of length }\le r\ ? \]

QUICK LITERATURE/CONTEXT CHECK

This question is listed as Erdős Problem #740 and marked open in the Erdős Problems Project. The page notes that Rödl proved the statement for $(\mathfrak m,r)=(\aleph_0,3)$. For uncountable chromatic number, Komjáth and Shelah $1988$ discuss the related Erdős--Hajnal conjecture that every $\kappa$-chromatic graph contains a $\kappa$-chromatic triangle-free subgraph; they show the answer can be consistently negative for $\kappa=\aleph_1$.

ATTACK PLAN

  1. Proof-track: use known finitary "cleaning" theorems (Rödl for triangles) plus compactness to deduce the countable case; attempt to iterate for larger odd-girth thresholds.
  2. Disproof-track: search for (or cite) constructions of graphs of uncountable chromatic number whose triangle-free (or bounded odd-girth) subgraphs necessarily have smaller chromatic number.
  3. Best path here: record the strongest unconditional results (notably the $\aleph_0$, $r=3$ case) and explain why ZFC-resolution for general $(\mathfrak m,r)$ remains out of reach, including known consistency results.

WORK

1. The case $(\mathfrak m,r)=(\aleph_0,3)$ from a finitary input

We record a standard reduction from a finitary triangle-cleaning theorem to the countably infinite conclusion.
Theorem (Countable case, assuming finitary Rödl): Assume the following finitary statement:
For every $k\in\mathbb{N}$ there exists $N(k)\in\mathbb{N}$ such that every finite graph $F$ with $\chi(F)\ge N(k)$ contains a triangle-free subgraph $F'\subseteq F$ with $\chi(F')\ge k$.
Then every graph $G$ with $\chi(G)=\aleph_0$ contains a triangle-free subgraph $H\subseteq G$ with $\chi(H)=\aleph_0$.
Proof: Let $G$ be a graph with $\chi(G)=\aleph_0$. We build vertex-disjoint finite induced subgraphs $G[S_k]$ with very large chromatic numbers.

Step 1: Disjoint high-chromatic finite induced subgraphs exist. We claim that for every finite set $S\subseteq V(G)$, the graph $G\setminus S$ still has infinite chromatic number. Indeed, if $\chi(G\setminus S)\le t$ for some $t\in\mathbb{N}$, then coloring $G\setminus S$ with $t$ colors and giving each vertex of $S$ a fresh new color yields a proper coloring of $G$ with $t+|S|$ colors, contradicting $\chi(G)=\aleph_0$.

Hence, inductively, we may choose finite, pairwise disjoint sets $S_1,S_2,\dots$ such that \[\chi(G[S_k])\ge N(k)\qquad\text{for each }k\ge 1.\] (Choose $S_k$ inside $G\setminus (S_1\cup\cdots\cup S_{k-1})$ using de Bruijn--Erdős compactness.)

Step 2: Apply the finitary input on each piece. By the assumed finitary statement, each finite graph $G[S_k]$ has a triangle-free subgraph $H_k\subseteq G[S_k]$ with $\chi(H_k)\ge k$.

Step 3: Take the disjoint union as a subgraph of $G$. Let $H$ be the subgraph of $G$ with vertex set $\bigcup_{k\ge 1} S_k$ and edge set \[ E(H):=\bigcup_{k\ge 1} E(H_k).\] That is, we keep the edges of $H_k$ inside each block and delete all edges between distinct blocks. This is allowed because $H$ is only required to be a (not induced) subgraph.

Then $H$ is triangle-free (a triangle would have to lie within one block, but each $H_k$ is triangle-free), and \[\chi(H)=\sup_{k\ge 1}\chi(H_k)=\aleph_0\] because $\chi(H)\ge \chi(H_k)\ge k$ for each $k$. ∎

Remark. The cited Erdős Problems Project notes that Rödl proved the $(\aleph_0,3)$ case (and points to a finitary version). The argument above explains one way the countable conclusion follows from a finitary triangle-cleaning theorem.

2. Uncountable chromatic number: consistency obstacles

Komjáth and Shelah $1988$ studied the uncountable analogue of the triangle-cleaning problem and showed (by forcing) that it is consistent with ZFC that there exists a graph $X$ on $\omega_1$ with $\chi(X)=\aleph_1$ such that every triangle-free subgraph of $X$ is only countably chromatic. In such a model, the answer to the $r=3$ instance of the question is negative for $\mathfrak m=\aleph_1$. They emphasize that a ZFC counterexample is not known there.

VERIFICATION

  • In the countable-case theorem, the construction deletes all inter-block edges, ensuring triangle-freeness even if $G$ has many edges between blocks.
  • The key subtlety is obtaining vertex-disjoint finite induced subgraphs with large chromatic number; the argument that removing finitely many vertices cannot drop $\chi$ from $\aleph_0$ to finite is correct.
  • The "uncountable" paragraph is explicitly stated as a consistency statement rather than a ZFC theorem.

FINAL

UNRESOLVED (in ZFC) for general $(\mathfrak m,r)$.

(i) Strongest fully proved partial result obtained here. Assuming a finitary triangle-cleaning theorem (Rödl-type), one can rigorously deduce the case $(\mathfrak m,r)=(\aleph_0,3)$: every $\aleph_0$-chromatic graph contains a triangle-free subgraph of chromatic number $\aleph_0$. Also, there are consistency results (Komjáth--Shelah) showing that for $\mathfrak m=\aleph_1$ the $r=3$ statement can fail in some models of ZFC.

(ii) First gap. A ZFC-resolution (either proof or explicit ZFC counterexample) for uncountable $\mathfrak m$ already when $r=3$ is not supplied by the consistency results; similarly, extending from $r=3$ to larger odd-girth thresholds is open in general.

(iii) Top 3 next moves.

  1. Determine whether the $r=3$ statement for $\mathfrak m=\aleph_1$ is decidable in ZFC (prove it or build an explicit ZFC counterexample).
  2. Seek a framework to "clean" odd cycles of lengths $\le r$ while preserving large chromatic number, generalizing Rödl's approach beyond triangles.
  3. Analyze whether additional set-theoretic hypotheses (large cardinals, forcing axioms) yield positive or negative answers, clarifying the independence landscape.

(iv) What a minimal counterexample would likely look like. For $r=3$ and uncountable $\mathfrak m$, a minimal counterexample would be a graph $G$ with $\chi(G)=\mathfrak m$ such that every triangle-free subgraph has chromatic number $<\mathfrak m$. Known forcing constructions achieve this behavior for $\mathfrak m=\aleph_1$ in some models, suggesting that any ZFC counterexample (if it exists) may require delicate combinatorial set-theory.

COMPLETION ESTIMATE

COMPLETION: 45%.

References

  • [GyarfasPfree] M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski, S. Thomassé, and B. Walczak, Degeneracy of $P_t$-free and $C_{\ge t}$-free graphs with no large complete bipartite subgraphs,
    arXiv:2012.03686. (Abstract recalls Gyárfás' 1985 bound for $P_t$-free graphs.)
  • [GyarfasSzTuza] A. Gyárfás, E. Szemerédi, and Z. Tuza, Induced subtrees in graphs of large chromatic number,
    Discrete Mathematics 30 $1980$, 235--244.
  • [ScottInducedTrees] A. D. Scott, Induced trees in graphs of large chromatic number,
    Journal of Graph Theory 24$4$ $1997$, 297--311.
    (Topological/subdivision version of Gyárfás--Sumner.)
  • [KomjathShelah1988] P. Komjáth and S. Shelah, For uncountably chromatic graphs,
    Journal of Symbolic Logic 53 $1988$, 695--703.
    (Consistency results for uncountably chromatic graphs and triangle-free subgraphs; see also the discussion in §1.)