The nebula conjecture

About 5 years old · traced to

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.

References

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.