Robust Bollobás–Eldridge–Catlin universality conjecture
For , let denote the threshold function for the appearance of a -factor in a random graph, and let be the random subgraph obtained by retaining each edge of independently with probability . Let -universality mean containing every graph on at most vertices with maximum degree at most .
Robust universality conjecture. For any , there exists a constant such that, for all and , every graph with satisfies that is -universal with high probability.
This is presented as a common strengthening of the Bollobás–Eldridge–Catlin conjecture and the random-graph universality threshold. The parser marks it resolved, although the surrounding text describes it as a conjectural robustness statement; the claimed resolution should be checked against the cited source context.
References
Primary source
Peter Allen, Julia Böttcher, Jan Corsten, Ewan Davies, Matthew Jenssen, Patrick Morris, Barnaby Roberts and Jozef Skokan, “A robust Corrádi–Hajnal Theorem”, arXiv:2209.01116 (2026).
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
No solutions have been posted yet.