Robust Bollobás–Eldridge–Catlin universality conjecture

About 4 years old · traced to

For 2≤k2\leq k, let pk+1∗p^*_{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 k≥2k\geq 2, there exists a constant C>0C>0 such that, for all n∈Nn\in\mathbb N and p≥Cpk+1∗p\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.

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

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.