Back to Search Start Over

Universality for graphs with bounded density

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

Abstract

A graph $G$ is $\textit{universal}$ for a (finite) family $\mathcal{H}$ of graphs if every $H \in \mathcal{H}$ is a subgraph of $G$. For a given family $\mathcal{H}$, the goal is to determine the smallest number of edges an $\mathcal{H}$-universal graph can have. With the aim of unifying a number of recent results, we consider a family of graphs with bounded density. In particular, we construct a graph with $O_d\left( n^{2 - 1/(\lceil d \rceil + 1)} \right)$ edges which contains every $n$-vertex graph with density at most $d \in \mathbb{Q}$ ($d \ge 1$), which is close to a lower bound $\Omega(n^{2 - 1/d - o(1)})$ obtained by counting lifts of a carefully chosen (small) graph. When restricting the maximum degree of such graphs to be constant, we obtain a near-optimal universality. If we further assume $d \in \mathbb{N}$, we get an asymptotically optimal construction.<br />Comment: 14 pages, updated version focusing on density, with new title and additional author

Subjects

Subjects :
Mathematics - Combinatorics
05C35

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2311.05500
Document Type :
Working Paper