Universality conjecture for graphs with bounded density
Universality conjecture for graphs with bounded density
For and , let be the family of all graphs with vertices and density at most , where the density of a graph is
A graph is -universal if it contains every graph in as a subgraph. Bounded-density universality conjecture. For every with and every , there exists a graph with
edges which is -universal, where . This conjecture would unify the known and almost-optimal universality bounds for several families whose properties bound their density; the general bounded-density case remains open.
Sources & referencesView supporting material
Primary source
Noga Alon, Natalie Dodson, Carmen Jackson, Rose McCarty, Rajko Nenadov and Lani Southern, “Universality for graphs with bounded density”, arXiv:2311.05500 (2024).
Additional references
2 papers in this index state this conjecture (2006–2023). The statement above is taken from the most recent of them; the others are arXiv:math/0611321.
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
Sign in to submit a solution.
No solutions have been posted yet.