Erdős–Hajnal hypergraph Ramsey conjecture

For every pair of integers $s>k\ge 4$ , there exists a constant $c=c(s,k)>0$ such that, for all sufficiently large integers $n$ , $r_k(s,n)\ge \operatorname{twr}_{k-1}(cn)$ . Here $r_k(s,n)$ is the least integer $N$ such that every $k$ -uniform hypergraph on $N$ vertices contains either a complete $k$ -uniform hypergraph $K_s^{(k)}$ or an independent set of size $n$ , and $\operatorname{twr}_1(x)=2^x$ and $\operatorname{twr}_{j+1}(x)=2^{\operatorname{twr}_j(x)}$ .

References

Primary source

arXiv

Additional references

The Erdős--Hajnal hypergraph Ramsey problem for r_4(6,n) — arXiv — Longma Du, Xinyu Hu, Ruilong Liu, Guanghui Wang

extremal-combinatorics ramsey-theory

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed progress

A September 2026 paper claims a major lower-bound advance for one family of hypergraph Ramsey numbers, but the full conjecture remains open.

The Erdős–Hajnal conjecture concerns tower-type lower bounds for off-diagonal hypergraph Ramsey numbers. The latest claim establishes the target family $r_4(6,n)$ and, by stepping up, the corresponding $r_k(k+2,n)$ consequence for every fixed $k \ge 4$ .

Known results

The 2016 treatment obtained tower bounds in many parameter ranges but left the $k+2$ cases, including $r_4(6,n)$ , unresolved: $r_4(6,n) \ge 2^{2^{\Omega(n^{1/2})}}$ was not reached.
A 2020 paper settled nearby families such as $r_k(k+1,k-1;n)=\operatorname{twr}_{k-2}(n^{\Theta(1)})$ , while leaving the relevant remaining cases open.

September 2026 claimed bound

A September 22, 2026 report attributes to Longma Du, Xinyu Hu, Ruilong Liu, and Guanghui Wang the bound $r_4(6,n) \ge 2^{2^{cn}}$ , with the fixed- $k$ consequence for $r_k(k+2,n)$ , $k \ge 4$ . This is substantial claimed progress, not a verified resolution of the broader conjecture.

Current status (as of September 2026): the $r_4(6,n)$ bound and its fixed- $k$ $r_k(k+2,n)$ consequence are claimed but unverified; the full Erdős–Hajnal conjecture remains open.

Sources

No solutions have been posted yet.