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

At least 1 year old · documented by

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.

References

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.