The nebula conjecture
The nebula conjecture
Let 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 , there exists such that every -free tournament on vertices contains a transitive subtournament of size at least . 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
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.