gpt pro 5.2 attempt on Math-5867

Problem 750: infinite chromatic number with near-half independent sets in every finite subgraph

1) FORMAL RESTATEMENT

Let $f:\mathbb{N}\to\mathbb{N}$ be a function with $f(m)\to\infty$ as $m\to\infty$. Does there exist a graph $G$ with infinite chromatic number $\chi(G)=\infty$ such that every (induced) subgraph $H$ of $G$ on $m$ vertices satisfies \[ \alpha(H)\ \ge\ \frac{m}{2} - f(m), \] where $\alpha(H)$ denotes the independence number?

(As usual, it suffices to consider induced subgraphs: deleting edges can only increase $\alpha$.)

2) QUICK LITERATURE/CONTEXT CHECK

Web browsing available? YES.

• The problem is listed as open on erdosproblems.com (Problem 750).
• For linear error terms $f(m)=\epsilon m$, this follows from a theorem of Erdős, Hajnal and Szemerédi $1982$ constructing graphs with arbitrarily large chromatic number and whose finite induced subgraphs are "almost bipartite".

3) ATTACK PLAN

• Exploit almost-bipartite constructions: If every $m$-vertex induced subgraph contains a bipartite induced subgraph on $(1-\delta)m$ vertices, then it has an independent set of size at least $(1-\delta)m/2$. This gives the desired inequality with $f(m)=\delta m/2$.
• Upgrade to infinite chromatic number: Take a disjoint union of graphs with arbitrarily large finite chromatic number, all satisfying the same local "almost bipartite" property.
• Hard part: To reach arbitrary $f(m)\to\infty$ (e.g. $f(m)=\log m$) one would need $\delta=\delta(m)\to 0$, i.e. finite subgraphs becoming asymptotically bipartite. This is the genuinely open regime.

4) WORK

4.1 A proved special case: $f(m)$ linear.

The following is a clean implication of the Erdős--Hajnal--Szemerédi (EHS) theorem.

Theorem 4.1 (EHS $\Rightarrow$ Erdős conjecture for $f(m)=\epsilon m$). Fix $\epsilon>0$. There exists a graph $G$ with $\chi(G)=\infty$ such that every finite induced subgraph $H$ on $m$ vertices satisfies \[ \alpha(H)\ \ge\ \left(\frac12-\epsilon\right)m. \]

Proof. EHS $1982$ prove (in particular) that for every $\delta>0$ and every integer $k$ there is a graph $G_{k,\delta}$ with $\chi(G_{k,\delta})>k$ such that every finite vertex set $U$ in $G_{k,\delta}$ contains an induced bipartite subgraph on more than $(1-\delta)|U|$ vertices. (Equivalently, their function $f^2_{G_{k,\delta}}(n)$ satisfies $f^2_{G_{k,\delta}}(n)>(1-\delta)n$ for all $n$.)

Let $\delta:=2\epsilon$ and for each $k\ge 1$ pick such a graph $G_k:=G_{k,2\epsilon}$. Now form the disjoint union \[ G:=\bigsqcup_{k\ge 1} G_k. \] Then $\chi(G)=\sup_k \chi(G_k)=\infty$.

Let $H$ be any induced subgraph of $G$ on $m$ vertices. It decomposes as a disjoint union of induced subgraphs $H_k$ of each component $G_k$: \[ V(H)=\bigsqcup_k V(H_k),\qquad |V(H_k)|=:m_k,\qquad \sum_k m_k=m. \] Inside each $H_k$, EHS gives an induced bipartite subgraph on at least $(1-2\epsilon)m_k$ vertices. Any bipartite graph on $t$ vertices has an independent set of size at least $t/2$ (take the larger side of a bipartition). Therefore \[ \alpha(H_k)\ \ge\ \frac{(1-2\epsilon)m_k}{2}=\left(\frac12-\epsilon\right)m_k. \] Since components are disjoint, independent sets add: \[ \alpha(H)\ =\ \sum_k \alpha(H_k)\ \ge\ \left(\frac12-\epsilon\right)\sum_k m_k=\left(\frac12-\epsilon\right)m. \] $\square$

Thus the question has a complete answer for all functions $f$ with $f(m)\ge \epsilon m$ for some fixed $\epsilon>0$.

4.2 Why the general $f(m)\to\infty$ case is harder.

If $f(m)=o(m)$, the required lower bound is \[ \alpha(H)\ \ge\ \frac{m}{2}-o(m), \] so every large finite induced subgraph would have to be asymptotically bipartite (up to deleting $o(m)$ vertices). EHS provides only a fixed proportional deletion $\delta m$ (with $\delta$ fixed in advance). Whether one can make $\delta=\delta(m)\to 0$ while keeping $\chi(G)=\infty$ is exactly the delicate open direction.

5) VERIFICATION

• Verified that the disjoint-union argument preserves the $(\frac12-\epsilon)m$ independent-set property because the bound is linear in $m$.
• Verified that the step "bipartite $\Rightarrow$ independent set $\ge t/2$" is immediate from the definition of bipartite.
• The remaining gap is not a proof issue but a genuine strengthening beyond what EHS guarantees.

6) FINAL

UNRESOLVED.

• What I have: A complete proof for the Erdős conjectured linear regime $f(m)=\epsilon m$ (Theorem 4.1), via EHS $1982$.
• Where it breaks: For sublinear $f(m)$ one would need "almost bipartite with $o(m)$ deletions" for every $m$-vertex subgraph, which is not provided by existing arguments in EHS and is the open core.
• Next moves:
  1. Investigate whether EHS-type probabilistic constructions can be iterated with a diagonal/compactness argument to force $\delta(m)\to 0$ on larger and larger scales without collapsing chromatic number.
  2. Search for obstructions: prove lower bounds showing that $\chi(G)=\infty$ forces some finite subgraphs to have $\alpha(H)\le m/2 - c(m)$ with $c(m)\to\infty$ (which would refute the statement for some slowly growing $f$).
• Minimal lemma that would settle the full problem (one route): For any function $\delta(m)\downarrow 0$, construct a graph $G$ with $\chi(G)=\infty$ such that every $m$-vertex induced subgraph contains an induced bipartite subgraph on at least $(1-\delta(m))m$ vertices. Taking $\delta(m)=2f(m)/m$ would then imply $\alpha(H)\ge m/2-f(m)$.

7) COMPLETION

COMPLETION: 60% (full solution for the linear case; general $f(m)\to\infty$ remains open).