Drier–Linial conjecture on the Hajós number of random lifts

An \ell-lift of KnK_n is obtained by replacing every vertex of KnK_n with an independent set of size \ell and every edge with a matching of size \ell between the corresponding fibers. Say that almost all \ell-lifts of KnK_n have a property if all but a vanishing proportion do as nn\to\infty. The Hajós number of a graph is the largest order of a topological clique occurring as a subgraph. Drier–Linial conjecture. For Ω(n)\ell\geq\Omega(n), almost all \ell-lifts of KnK_n have Hajós number equal to Θ(n)\Theta(n). Drier and Linial established a linear lower bound when <(1o(1))n/2\ell<(1-o(1))n/2, 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

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.