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 SS, a nonnegative real number ϵ\epsilon is an EH-coefficient if there exists c>0c>0 such that every SS-free tournament TT satisfies α(T)cV(T)ϵ\alpha(T)\geq c|V(T)|^\epsilon, where α(T)\alpha(T) 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 cc 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

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.