gpt pro 5.2 attempt on Math-6165

FORMAL RESTATEMENT

Let $G$ be a finite (simple) graph. For disjoint vertex sets $A,B\subseteq V(G)$, say $A$ and $B$ are anticomplete if there are no edges between $A$ and $B$. Write $\chi(G)$ for chromatic number and $\omega(G)$ for clique number. For a vertex subset $X\subseteq V(G)$, write $\chi(X)$ for the chromatic number of the induced subgraph $G[X]$.

The statement in the problem file is:

For all integers $t,c\ge 1$ there exists an integer $d\ge 1$ such that if $\chi(G)\ge d$ and $\omega(G)<t$, then there exist disjoint anticomplete sets $A,B\subseteq V(G)$ with $\chi(A)\ge \chi(B)\ge c$.

Let $d(t,c)$ be the minimal such $d$.

QUICK LITERATURE/CONTEXT CHECK

The problem file attributes this to El Zahar and Erdős. It states that a result of Wagon implies $d(t,2)\le \binom{t}{2}+1$, and lists exact small values $d(2,2)=2$, $d(3,2)=4$, $d(4,2)=5$. It also notes a 2024 result of Nguyen--Scott--Seymour proving a related statement: existence of anticomplete $A,B$ with $\chi(B)\ge c$ and minimum degree in $G[A]$ at least $c$. I do not use any external results beyond what is explicitly stated in the problem text.

ATTACK PLAN

Proof-track strategies.

• Start with small $c$: for $c=1$ the statement reduces to finding two nonadjacent vertices; for $c=2$ it is equivalent to forcing an induced $2K_2$ (an induced matching of size $2$).
• For general $c$, attempt to build two anticomplete induced subgraphs each requiring $c$ colors via iterative neighborhood decompositions or via a minimal counterexample approach.
• Use clique-number bounds to control how chromatic number can concentrate in neighborhoods, and search for two far-apart high-chromatic regions.

Disproof-track strategies. Attempt to construct graphs with bounded clique number but arbitrarily large chromatic number in which every pair of anticomplete sets has one side with small chromatic number (e.g. by forcing every large-chromatic subgraph to be highly connected to the rest).

WORK

FAST REALITY CHECK (small cases).

• If $c=1$, the conclusion asks for two nonempty anticomplete sets, which is equivalent to the existence of two nonadjacent vertices.
• For $(t,c)=(3,2)$ (triangle-free, seeking two anticomplete sets each of chromatic number $\ge 2$): the 5-cycle $C_5$ is triangle-free and has $\chi(C_5)=3$, but it contains no induced $2K_2$ (every 4-vertex induced subgraph is a path $P_4$), so $d(3,2)\ge 4$.

Lemma 1111.1 (the case $c=1$: exact value $d(t,1)=t$).

For every integer $t\ge 2$, we have $d(t,1)=t$.

Proof.

Upper bound $d(t,1)\le t$. Assume $\chi(G)\ge t$ and $\omega(G)<t$. If $G$ were complete on $n$ vertices then $\chi(G)=n$ and $\omega(G)=n$, so $\chi(G)\ge t$ would imply $\omega(G)\ge t$, contradicting $\omega(G)<t$. Thus $G$ is not complete, so there exist two nonadjacent vertices $u\ne v$. Then $A=\{u\}$ and $B=\{v\}$ are disjoint and anticomplete, and $\chi(A)=\chi(B)=1$. This proves the conclusion for $c=1$ with $d=t$.

Lower bound $d(t,1)\ge t$. Consider the complete graph $K_{t-1}$. It satisfies $\omega(K_{t-1})=t-1<t$ and $\chi(K_{t-1})=t-1$. However, $K_{t-1}$ has no pair of nonempty anticomplete vertex sets, because every two distinct vertices are adjacent. Therefore any $d< t$ fails the defining property of $d(t,1)$. Hence $d(t,1)=t$. $\square$

Lemma 1111.2 (equivalence for $c=2$ with induced $2K_2$).

A graph $G$ contains an induced subgraph isomorphic to $2K_2$ (two disjoint edges with no other edges among the four vertices) if and only if $G$ has disjoint anticomplete vertex sets $A,B$ with $\chi(A)\ge 2$ and $\chi(B)\ge 2$.

Proof.

($\Rightarrow$) If $G$ has an induced $2K_2$ on vertex set $\{a_1,a_2,b_1,b_2\}$ with edges $a_1a_2$ and $b_1b_2$, let $A=\{a_1,a_2\}$ and $B=\{b_1,b_2\}$. Then there are no edges between $A$ and $B$ by the definition of induced $2K_2$. Also $G[A]$ contains an edge, so $\chi(A)\ge 2$, and similarly $\chi(B)\ge 2$.

($\Leftarrow$) Conversely, assume there exist disjoint anticomplete $A,B$ with $\chi(A)\ge 2$ and $\chi(B)\ge 2$. Then $G[A]$ contains an edge $a_1a_2$, and $G[B]$ contains an edge $b_1b_2$. Since $A$ and $B$ are anticomplete, there are no edges between $\{a_1,a_2\}$ and $\{b_1,b_2\}$. Thus the induced subgraph on $\{a_1,a_2,b_1,b_2\}$ is exactly two disjoint edges, i.e. an induced $2K_2$. $\square$

Lemma 1111.3 (exact value $d(3,2)=4$).

We have $d(3,2)=4$. Equivalently: every triangle-free graph with chromatic number at least $4$ contains an induced $2K_2$.

Proof.

Lower bound. As noted in the fast reality check, $C_5$ is triangle-free with $\chi(C_5)=3$ and contains no induced $2K_2$. Thus $d(3,2)\ge 4$.

Upper bound. Let $G$ be triangle-free and suppose $G$ contains no induced $2K_2$. We prove $\chi(G)\le 3$ by constructing an explicit 3-coloring.

If $G$ has no edges then $\chi(G)=1$ and we are done. Otherwise choose an edge $uv$. Define three vertex sets: \[A:=N(u)\setminus\{v\},\qquad B:=N(v)\setminus\{u\},\qquad C:=V(G)\setminus\left(N[u]\cup N[v]\right),\] where $N(x)$ is the neighborhood and $N[x]=N(x)\cup\{x\}$.

Because $G$ is triangle-free, the neighborhood of any vertex is independent. In particular, $A$ is independent (all are neighbors of $u$) and $B$ is independent (all are neighbors of $v$). Also, if $x\in A$ then $x$ is adjacent to $u$, so $x$ cannot be adjacent to $v$ (otherwise $u,v,x$ would be a triangle). Hence there are no edges between $A$ and $\{v\}$. Similarly, there are no edges between $B$ and $\{u\}$.

Next, we show $C$ is independent. Suppose for contradiction that $xy$ is an edge with $x,y\in C$. By definition of $C$, neither $x$ nor $y$ is adjacent to $u$ or $v$. Thus the induced subgraph on $\{u,v,x,y\}$ consists of the two disjoint edges $uv$ and $xy$, with no other edges among these four vertices, i.e. an induced $2K_2$. This contradicts the assumption that $G$ has no induced $2K_2$. Therefore $C$ is independent.

Now define a 3-coloring by the three independent sets \[\text{Color 1: } A\cup\{v\},\qquad \text{Color 2: } B\cup\{u\},\qquad \text{Color 3: } C. \] We already checked $A$ is independent and $v$ has no neighbors in $A$, so Color 1 is independent. Similarly Color 2 is independent. Color 3 is independent since $C$ is independent. Therefore this is a proper 3-coloring, so $\chi(G)\le 3$.

By contrapositive, any triangle-free graph with $\chi(G)\ge 4$ must contain an induced $2K_2$, which by Lemma 1111.2 yields the desired anticomplete sets with chromatic number at least $2$. Thus $d(3,2)\le 4$. Combining with the lower bound gives $d(3,2)=4$. $\square$

VERIFICATION

• Lemma 1111.1: the only subtlety is ensuring that $\chi(G)\ge t$ and $\omega(G)<t$ forces $G$ not complete; this was checked by comparing $\chi$ and $\omega$ for complete graphs.
• Lemma 1111.2: in the ($\Leftarrow$) direction, we used that $\chi(X)\ge 2$ implies $G[X]$ contains an edge. This is valid for induced subgraphs of simple graphs: if $G[X]$ had no edges it would be 1-colorable.
• Lemma 1111.3: the key step is proving $C$ is independent; this uses the definition of $C$ (no adjacency to $u$ or $v$) and the fact that $uv$ is an edge.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For $c=1$ we proved the exact value $d(t,1)=t$ (Lemma 1111.1). For $(t,c)=(3,2)$ we proved the exact value $d(3,2)=4$ (Lemma 1111.3), via the equivalence with induced $2K_2$ (Lemma 1111.2).

(ii) First gap. For general $t,c\ge 2$, prove (or refute) the existence of a finite bound $d(t,c)$ guaranteeing anticomplete sets $A,B$ with $\chi(A)\ge \chi(B)\ge c$ whenever $\chi(G)$ is large and $\omega(G)<t$.

(iii) Top 3 next moves. 1. Try to generalize the $c=2$ argument: characterize graphs with no pair of anticomplete induced subgraphs of chromatic number $\ge c$ and attempt to bound their chromatic number in terms of $\omega$. 2. Investigate whether the Nguyen--Scott--Seymour 2024 strengthening (anticomplete $A,B$ with $\chi(B)\ge c$ and $\delta(G[A])\ge c$) can be combined with additional structure to force $\chi(A)\ge c$. 3. Compute/construct potential extremal examples for small $(t,c)$ beyond $(3,2)$, to guess sharp values and to identify structural obstructions.

(iv) What a minimal counterexample would likely look like. A minimal counterexample for fixed $(t,c)$ would be a graph with $\omega(G)<t$ and very large $\chi(G)$ in which every induced subgraph of chromatic number $\ge c$ has its vertex set highly adjacent to any other such subgraph (so that two such subgraphs cannot be anticomplete). One expects such a graph to have strong expansion or to be built by iterated substitutions/blow-ups that prevent large anticomplete separations.