The positive EH-coefficient conjecture for tournaments
The positive EH-coefficient conjecture for tournaments
A tournament is a directed graph with exactly one directed edge between each pair of distinct vertices. For a tournament , a nonnegative real number is an EH-coefficient if there exists such that every -free tournament satisfies , where is the maximum size of a transitive subtournament.
Positive EH-coefficient conjecture. Every tournament has a positive EH-coefficient.
The source states that this is equivalent to the Erdős–Hajnal conjecture. Introducing the constant removes effects from tournaments of bounded order; the conjecture remains open in general.
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.