Strong Erdős–Hajnal conjecture for simple digraphs

From papers

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 εT2/t\varepsilon_T\leq 2/t when TT has t3t\geq3 vertices, while the general conjecture remains open.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.