The tournament Erdős–Hajnal conjecture
The tournament Erdős–Hajnal conjecture
A tournament is a directed graph in which exactly one of and is an edge for every pair of distinct vertices. A tournament is -free if it has no subtournament isomorphic to . Let be the maximum number of vertices in a transitive subtournament of .
Tournament Erdős–Hajnal conjecture. For every tournament , there exists a constant such that every -free tournament satisfies
The source states this as equivalent to the graph Erdős–Hajnal conjecture. Transitive subtournaments provide a single analogue of cliques and stable sets, but the conjecture remains open in general; the exponent in the source is written as despite the quantified tournament being .
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, “The Erdös-Hajnal Conjecture—A Survey”, arXiv:1606.08827 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.