Alon–Pachs–Solymosi conjecture on acyclic sets in H-free tournaments

Let HH be a tournament. An HH-free tournament is one that does not contain HH as a not necessarily induced subdigraph. For a tournament TT, write α(T)\vec\alpha(T) for its maximum acyclic set size. Alon–Pachs–Solymosi conjecture. For every tournament HH, there exists ϵ>0\epsilon>0 such that every HH-free tournament TT of order nn satisfies

α(T)nϵ.\vec\alpha(T)\geq n^\epsilon.

This conjecture is equivalent to the Erdős–Hajnal conjecture. It is known for a few types of tournaments HH, but remains wide open in general.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Frédéric Havet, François Pirot and Juliette Schabanel, “Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order”, arXiv:2403.02298 (2024).

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.