Erdős Problem #579

Erdős Problem 579 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/579.tex.

REUSED SOURCE 1

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.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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.