Erdős–Hajnal: clique size forced when every 7 vertices span a triangle — estimate $h(n)$ (Erdős #813)
Statement
Let $h(n)$ be the largest integer such that every graph on $n$ vertices in which every set of $7$ vertices contains a triangle (a copy of $K_3$) must contain a clique (complete subgraph) on at least $h(n)$ vertices. Estimate the growth of $h(n)$. In particular, do there exist constants $c_1,c_2>0$ such that $$n^{1/3+c_1}\ll h(n)\ll n^{1/2-c_2}\,?$$ Equivalently, is the exponent of $h(n)$ bounded strictly inside the interval $(1/3,1/2)$, and what is its exact value?
Acceptance. FULLY RESOLVES: determine the exponent of $h(n)$ — a proof that $h(n)=n^{\alpha+o(1)}$ for an explicit $\alpha$ (with matching upper and lower bounds), or more strongly the asymptotics of $h(n)$; equivalently, decide whether the exponent lies strictly inside $(1/3,1/2)$ and pin its value. Complete written proof (machine-checkable preferred). ADVANCES: prove a new upper or lower bound strictly improving those in the background — a lower bound with exponent exceeding $5/12$, or the first upper bound of the form $h(n)\ll n^{1/2-c_2}$ with an explicit $c_2>0$ (which requires an explicit graph family that has the 7-vertices-force-a-triangle property yet clique number $\ll n^{1/2-c_2}$, delivered with a proof or verifier of both properties) — with a full proof. Deliver the proof, and for constructions the explicit graph family plus the certified clique-number bound.
Background
A problem of Erdős and Hajnal [Er91]. Listed as open on erdosproblems.com/813 (fetched 2026-07-13, status 'open', tagged 'graph theory'). The hypothesis 'every $7$ vertices contain a triangle' is a local density condition (no $6$ vertices induce a triangle-free subgraph), and the question is how large a global clique it guarantees. Erdős and Hajnal established the base bounds $n^{1/3}\ll h(n)\ll n^{1/2}$. Bucić and Sudakov [BuSu23] improved the lower bound to $h(n)\gg n^{5/12-o(1)}$ (note $5/12=0.41\overline{6}$, comfortably above $1/3$), so a constant $c_1>0$ with $h(n)\gg n^{1/3+c_1}$ is now known; the upper side — whether the exponent is bounded away from $1/2$ (i.e. whether such a $c_2>0$ exists) — remains open, as does the exact exponent. Attacker's tool: extremal constructions of graphs having the '7-vertices-force-a-triangle' property but small clique number (to bound the exponent below $1/2$), Ramsey-type and dependent-random-choice arguments for the lower bound, and exhaustive search on small $n$ to inform the extremal exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #813 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.