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

About 2 years old · traced to

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 n→∞n\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 ℓ<(1−o(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.

References

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.