The nebula conjecture

Let TT be a tournament. A nebula is a tournament admitting an ordering whose vertices are partitioned into the vertex sets of stars and singleton components, with no restriction on whether a star is left or right and no condition on the locations of star centers. Nebula conjecture. Every nebula satisfies the Erdős–Hajnal conjecture; equivalently, for every nebula HH, there exists ϵ(H)>0\epsilon(H)>0 such that every HH-free tournament on nn vertices contains a transitive subtournament of size at least nϵ(H)n^{\epsilon(H)}. Galaxies are known to satisfy the Erdős–Hajnal conjecture, but it is not known whether the result extends to nebulae after abandoning the galaxy condition on star centers.

Sources & referencesView supporting material

Primary source

Salman Ghazal and Soukaina Zayat, “Forbidding Couples of Tournaments and the Erdös-Hajnal Conjecture”, arXiv:2101.10754 (2021).

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.