gpt pro 5.2 attempt on Math-860

1) FORMAL RESTATEMENT

Let $K_{2,2,2}$ denote the complete $3$-partite graph with three parts of size $2$ (6 vertices total), i.e., between any two parts all $4$ cross edges are present.

For $\delta>0$, the claim is: \[ \exists c(\delta)>0\ \exists n_0(\delta)\ \forall n\ge n_0(\delta)\ \forall\text{ graphs }G\text{ on }n\text{ vertices}, \] if $G$ contains no $K_{2,2,2}$ subgraph and has at least $\delta n^2$ edges, then the independence number satisfies \[ \alpha(G)\ge c(\delta)\,n. \]

2) QUICK LITERATURE/CONTEXT CHECK

The source file states that Erdős, Hajnal, Sós, and Szemerédi could prove the statement for $\delta>1/8$. The Erdős Problems website currently lists #579 as open.

3) ATTACK PLAN

Proof-track ideas: - Reinterpret $K_{2,2,2}$-freeness in terms of common neighborhoods and $C_4$-freeness, then use density to force a large common neighborhood that is itself dense enough to contain a $C_4$ unless there is a large independent set. - Use double counting to show that dense graphs have many pairs with large common neighborhoods; combine with structural restrictions implied by $K_{2,2,2}$-freeness.

Disproof-track ideas: - Try to build dense $K_{2,2,2}$-free graphs with independence number $o(n)$. This is a Ramsey--Turán type construction problem; no explicit construction is produced here.

4) WORK

FAST REALITY CHECK (exact small $n$ computations). Exact maximum edges in $K_{2,2,2}$-free graphs (labeled, by exhaustive search over complements) for small $n$: \[ \mathrm{ex}(6;K_{2,2,2})=13,\qquad \mathrm{ex}(7;K_{2,2,2})=17,\qquad \mathrm{ex}(8;K_{2,2,2})=22. \] For $n=6$, among $K_{2,2,2}$-free graphs, the minimum possible independence number $\alpha$ as a function of edge count $m$ satisfies $\min\alpha=2$ for every $m\ge 6$ (in particular for all $m\ge \lceil (1/8)n^2\rceil=5$).

Lemma 579.1 (characterization via common neighborhoods). A graph $G$ contains a copy of $K_{2,2,2}$ as a (not necessarily induced) subgraph if and only if there exist two distinct vertices $u,v\in V(G)$ such that the induced subgraph on their common neighborhood $G[N(u)\cap N(v)]$ contains a copy of $C_4$.

Equivalently, $G$ is $K_{2,2,2}$-free if and only if for every pair $u\ne v$, the graph $G[N(u)\cap N(v)]$ is $C_4$-free. Proof. ($\Rightarrow$) Suppose $G$ contains a copy of $K_{2,2,2}$ with parts $A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$. Take $u=a_1$ and $v=a_2$. Then every vertex in $B\cup C$ is adjacent to both $u$ and $v$, so $B\cup C\subseteq N(u)\cap N(v)$. Within $K_{2,2,2}$, the four vertices $B\cup C$ span a complete bipartite graph $K_{2,2}$ (all edges between $B$ and $C$), which contains a 4-cycle (e.g. $b_1-c_1-b_2-c_2-b_1$). Hence $G[N(u)\cap N(v)]$ contains a $C_4$.

($\Leftarrow$) Conversely, suppose there exist $u\ne v$ such that $G[N(u)\cap N(v)]$ contains a 4-cycle on vertices $x_1,y_1,x_2,y_2$ with edges $x_1y_1,y_1x_2,x_2y_2,y_2x_1$. Because $x_i,y_i\in N(u)\cap N(v)$, each of $x_1,x_2,y_1,y_2$ is adjacent to both $u$ and $v$. The 4-cycle edges include all four cross edges between the pair $\{x_1,x_2\}$ and the pair $\{y_1,y_2\}$ (a $C_4$ is a $K_{2,2}$). Therefore the six vertices \[ \{u,v\}\cup\{x_1,x_2\}\cup\{y_1,y_2\} \] span a subgraph containing all edges between the three pairs; this is exactly a $K_{2,2,2}$ subgraph (additional edges within pairs are irrelevant for subgraph containment). Thus $G$ contains $K_{2,2,2}$. $\square$

Lemma 579.2 (dense graphs have a large common neighborhood). Let $G$ be an $n$-vertex graph with $m$ edges and degree sequence $d(v)$. Then \[ \max_{\{u,v\}\subseteq V(G)} |N(u)\cap N(v)| \ \ge\ \frac{\sum_{x\in V(G)} \binom{d(x)}{2}}{\binom{n}{2}}. \] In particular, if $m\ge \delta n^2$ for fixed $\delta>0$ and $n$ is large enough that $\frac{2m}{n}\ge 2$, then \[ \max_{\{u,v\}} |N(u)\cap N(v)|\ \ge\ (2\delta^2+o(1))\,n. \] Proof. For each unordered pair $\{u,v\}$, define the codegree $c(u,v)=|N(u)\cap N(v)|$. Each triple $(u,v,x)$ with $x$ adjacent to both $u$ and $v$ is counted exactly once in the sum $\sum_{\{u,v\}} c(u,v)$. Also, for a fixed vertex $x$, the number of unordered pairs $\{u,v\}$ contained in $N(x)$ is $\binom{d(x)}{2}$. Hence the double counting identity holds: \[ \sum_{\{u,v\}\subseteq V(G)} c(u,v) \,=\, \sum_{x\in V(G)} \binom{d(x)}{2}. \] Averaging over the $\binom{n}{2}$ unordered pairs $\{u,v\}$ gives \[ \frac{1}{\binom{n}{2}}\sum_{\{u,v\}} c(u,v) \,=\, \frac{\sum_x \binom{d(x)}{2}}{\binom{n}{2}}. \] Therefore the maximum codegree is at least the average codegree, proving the first inequality.

For the "in particular" bound, note that $\binom{d}{2}=\tfrac12(d^2-d)$ is convex in $d$, so by Jensen, \[ \frac{1}{n}\sum_x \binom{d(x)}{2} \ge \binom{\bar d}{2},\qquad \bar d:=\frac{1}{n}\sum_x d(x)=\frac{2m}{n}. \] Thus $\sum_x \binom{d(x)}{2} \ge n\binom{\bar d}{2}=\frac{n}{2}(\bar d^2-\bar d)$. If $m\ge \delta n^2$ then $\bar d=2m/n\ge 2\delta n$, so \[ \sum_x \binom{d(x)}{2} \ge \frac{n}{2}\big((2\delta n)^2-2\delta n\big)=2\delta^2 n^3 - \delta n^2. \] Dividing by $\binom{n}{2}=\frac{n(n-1)}{2}$ yields \[ \frac{\sum_x \binom{d(x)}{2}}{\binom{n}{2}} \ge \frac{2\delta^2 n^3-\delta n^2}{n(n-1)/2} = \frac{4\delta^2 n^2-2\delta n}{n-1} = (4\delta^2+o(1))n. \] This lower bounds the maximum codegree. (Any constant-factor variant, e.g. $(2\delta^2+o(1))n$, also follows for large $n$.) $\square$

Where the argument stalls. By Lemma 579.2, a $\delta n^2$-edge graph has a pair $u,v$ with a common neighborhood of linear size. By Lemma 579.1, $K_{2,2,2}$-freeness forces that common neighborhood to be $C_4$-free. To deduce a large independent set in $G$ from this, one would need an additional mechanism connecting global density and small $\alpha(G)$ to the presence of a $C_4$ inside some large common neighborhood. This is precisely the missing step.

5) VERIFICATION

- Lemma 579.1: checked both directions carefully using the fact that $C_4$ is the same as $K_{2,2}$ as a subgraph, and that subgraph embeddings allow extra edges within parts. - Lemma 579.2: checked the identity $\sum_{\{u,v\}}|N(u)\cap N(v)|=\sum_x \binom{d(x)}{2}$ by interpreting both sides as counting length-2 paths with distinct endpoints. - Small $n$ computations: validated by exhaustive search for $n=6$ and complement-search for $n=7,8$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result: $K_{2,2,2}$-freeness is equivalent to the condition that every common neighborhood is $C_4$-free (Lemma 579.1), and any graph with $\delta n^2$ edges contains a pair of vertices with a common neighborhood of size $\Omega_\delta(n)$ (Lemma 579.2).

(ii) First gap (crisp): Show that in a $K_{2,2,2}$-free graph with $e(G)\ge \delta n^2$ and $\alpha(G)=o(n)$, there must exist $u,v$ such that $G[N(u)\cap N(v)]$ contains a $C_4$ (contradicting Lemma 579.1).

(iii) Top 3 next moves (concrete): 1. Prove a density increment lemma: if $\alpha(G)$ is small and $e(G)\ge \delta n^2$, then some large common neighborhood $N(u)\cap N(v)$ must have edge density $\gg 1$, enough to force a $C_4$ by the $C_4$ extremal bound. 2. Try dependent random choice: in a dense graph with small independent set, find a set $U$ such that many pairs in $U$ have large and dense common neighborhoods. 3. Computation-guided: search for $K_{2,2,2}$-free graphs on $n=9,10$ with unusually small $\alpha(G)$ relative to edge density to guess extremal obstructions.

(iv) Minimal counterexample structure: A counterexample would be a family $G_n$ with $e(G_n)\ge \delta n^2$ and $\alpha(G_n)=o(n)$ while $G_n$ is $K_{2,2,2}$-free. By Lemma 579.2 such graphs have many large common neighborhoods; by Lemma 579.1 every such common neighborhood must be $C_4$-free, so the counterexample must enforce $C_4$-freeness on many induced subgraphs of linear order while still keeping global density quadratic.