Back to Search
Start Over
Universality for graphs with bounded density
- 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 :
- Mathematics - Combinatorics
05C35
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2311.05500
- Document Type :
- Working Paper