Drier–Linial conjecture on the Hajós number of random lifts
Drier–Linial conjecture on the Hajós number of random lifts
An -lift of is obtained by replacing every vertex of with an independent set of size and every edge with a matching of size between the corresponding fibers. Say that almost all -lifts of have a property if all but a vanishing proportion do as . The Hajós number of a graph is the largest order of a topological clique occurring as a subgraph. Drier–Linial conjecture. For , almost all -lifts of have Hajós number equal to . Drier and Linial established a linear lower bound when , while the conjecture addresses the larger-lift regime; the supplied text gives no evidence of a resolution.
Sources & referencesView supporting material
Primary source
Matija Bucić, Micha Christoph, Alp Müyesser and Raphael Steiner, “Topological Minors in Typical Lifts”, arXiv:2407.10565 (2024).
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.