Universality for bounded-density graph families

Conjecture 1.1 · arXiv:2311.05500

arXiv Conjecture high confidence— first stated 2024-01-11

Authors: Noga Alon, Natalie Dodson, Carmen Jackson, Rose McCarty, Rajko Nenadov, Lani Southern

Status open high confidence

Conjecture 1.1 of arXiv:2311.05500 asks for an $\mathcal{H}_d(n)$-universal graph with at most $Cn^{2-1/d}$ edges, which would be tight up to the constant $C$. The source paper itself proves a weaker construction with $O_d(n^{2-1/(\lceil d\rceil+1)})$ edges, achieving the bound only when $d\in\mathbb{N}$. A broad web search (5 calls) found no subsequent paper resolving or substantially advancing the general rational-$d$ case of this conjecture.

Reviewer notes. No follow-up found that resolves Conjecture 1.1 for non-integer rational d. Related work on hypergraph universality (arXiv:2511.23341, arXiv:2411.19432) appeared in 2024-2025 but could not be verified to address this specific conjecture within the 5-call budget. The paper has been published in a journal (ScienceDirect link found, likely J. Combin. Theory Ser. B). The gap between the proved bound O_d(n^{2-1/(ceil(d)+1)}) and the conjectured O_d(n^{2-1/d}) remains open for rational non-integer d.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every $d\in\mathbb{Q}$, $d>1$, and $n\in\mathbb{N}$, there exists a graph $G$ with $$e(G)\leq Cn^{2-1/d}$$ edges which is $\mathcal{H}_{d}(n)$-universal, where $C=C(d)$.

Context

The authors initiate the study of universality for graphs with bounded density, unifying earlier results on bounded-degree graphs, forests, and degenerate graphs. They note that a simple counting argument shows $e(G)=o(n^{2-1/d})$ is insufficient, making the conjectured bound tight up to the constant $C$. The paper proves constructions achieving $O_d(n^{2-1/(\lceil d\rceil+1)})$ edges, approaching but not yet matching this conjecture.

Also stated in

Universality for graphs with bounded density (2024-01-11)

Notes. The complete edge bound $e(G)\leq Cn^{2-1/d}$ appears in the introduction prose; the theorem-environment extraction was truncated. Statement reconstructed from the introduction.

Source paper

Universality for graphs with bounded density
Noga Alon, Natalie Dodson, Carmen Jackson, Rose McCarty, Rajko Nenadov, Lani Southern · 2024-01-11
https://arxiv.org/abs/2311.05500