Universality conjecture for graphs with bounded density

For dQd \in \mathbb{Q} and nNn \in \mathbb{N}, let Hd(n)\mathcal{H}_d(n) be the family of all graphs with nn vertices and density at most dd, where the density of a graph HH is

m(H)=maxHHe(H)v(H).m(H)=\max_{H'\subseteq H}\frac{e(H')}{v(H')}.

A graph is Hd(n)\mathcal{H}_d(n)-universal if it contains every graph in Hd(n)\mathcal{H}_d(n) as a subgraph. Bounded-density universality conjecture. For every dQd \in \mathbb{Q} with d>1d>1 and every nNn \in \mathbb{N}, there exists a graph GG with

e(G)Cn21/de(G)\leq C n^{2-1/d}

edges which is Hd(n)\mathcal{H}_d(n)-universal, where C=C(d)C=C(d). 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

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.