Robust Bollobás–Eldridge–Catlin universality conjecture

For 2k2\leq k, let pk+1p^*_{k+1} denote the threshold function for the appearance of a Kk+1K_{k+1}-factor in a random graph, and let GpG_p be the random subgraph obtained by retaining each edge of GG independently with probability pp. Let kk-universality mean containing every graph on at most nn vertices with maximum degree at most kk.

Robust universality conjecture. For any k2k\geq 2, there exists a constant C>0C>0 such that, for all nNn\in\mathbb N and pCpk+1p\geq Cp^*_{k+1}, every graph GG with δ(G)(kk+1)n\delta(G)\geq \big(\tfrac{k}{k+1}\big)n satisfies that GpG_p is kk-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.

Sources & referencesView supporting material

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

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.