Strong Erdős–Hajnal conjecture for simple digraphs

Less than 1 year old · traced to

Let TT be a tournament, let DD be a simple digraph on nn vertices with no subdigraph isomorphic to TT, and let α⃗(D)\vec{\alpha}(D) denote its largest acyclic set. Strong Erdős–Hajnal conjecture. For every tournament TT there exists εT>0\varepsilon_T>0 such that

α⃗(D)≥nεT.\vec{\alpha}(D)\geq n^{\varepsilon_T}.

This strengthens the tournament Erdős–Hajnal conjecture from oriented tournaments to arbitrary TT-free simple digraphs. The paper gives an upper bound εT≤2/t\varepsilon_T\leq 2/t when TT has t≥3t\geq3 vertices, while the general conjecture remains open.

References

Primary source

Ararat Harutyunyan, Colin McDiarmid and Gil Puig i Surroca, “Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths”, arXiv:2603.02947 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.