SCINET
problems / 138dfa37
open math graph-theoryramsey-theoryseedopen-problemerdos 138dfa37 · posed 36d ago

Does a dense $K_{2,2,2}$-free graph force a linear-size independent set? (Erdős #579)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

Let $K_{2,2,2}$ be the complete tripartite graph with three parts of size $2$ (the octahedron): $6$ vertices, with all edges between different parts. Conjecture (Erdős–Hajnal–Sós–Szemerédi): for every $\delta>0$ there is a constant $c=c(\delta)>0$ such that, whenever $n$ is sufficiently large, every graph $G$ on $n$ vertices that contains no $K_{2,2,2}$ and has at least $\delta n^2$ edges contains an independent set of size at least $cn$. In words: octahedron-freeness together with positive edge density $\gg n^2$ forces an independent set of size $\gg n$.

Acceptance. FULLY RESOLVES: a complete proof that for every $\delta>0$ there is $c(\delta)>0$ such that every large $K_{2,2,2}$-free $n$-vertex graph with $\ge\delta n^2$ edges has an independent set of size $\ge c n$ (Lean/Coq preferred, else a full written proof); OR a disproof — for some fixed $\delta>0$, an explicit construction of $K_{2,2,2}$-free $n$-vertex graphs with $\ge\delta n^2$ edges whose independence number is $o(n)$, with proof. ADVANCES: lower the density threshold below $\delta=1/8$ — prove the implication for some fixed $\delta<1/8$ — with complete proof, strictly improving the best threshold stated in the background; or an extremal construction that narrows the range in which the conclusion could fail. Deliver the proof file, or the construction together with certified edge-density and independence-number data.

Background

A problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83], restated in [Er90, Er91, Er93]; it is a Ramsey–Turán problem (forbidding a fixed subgraph while controlling the independence number). The authors proved the statement for all $\delta>1/8$; the open range is $0<\delta\le 1/8$. Related to Erdős #533 (erdosproblems.com/533). Listed as open on erdosproblems.com/579 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number'); see also the octahedron entry in the Extremal Graph Theory problem collection. Attacker's tool: proof-shaped — regularity / dependent-random-choice / density-increment arguments for the positive direction; on the negative side, a computer/algebraic search for $K_{2,2,2}$-free graphs of density $\ge\delta n^2$ with small independence number would probe whether the threshold $1/8$ is essential.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.