The Turán number of sparse spanning graphs

Noga Alon, Raphael Yuster

Authors: Noga Alon and Raphael Yuster

Abstract

For a graph $H$, the extremal number $ex(n,H)$ is the maximum number of edges in a graph of order $n$ not containing a subgraph isomorphic to $H$. Let $\delta(H) > 0$ and $\Delta(H)$ denote the minimum degree and maximum degree of $H$, respectively. We prove that for all $n$ sufficiently large, if $H$ is any graph of order $n$ with $\Delta(H) \le \sqrt{n}/200$, then $ex(n,H) = \binom{n-1}{2} + \delta(H) - 1$. The condition on the maximum degree is tight up to a constant factor. This generalizes a classical result of Ore for the case $H=C_n$, and resolves, in a strong form, a conjecture of Glebov, Person, and Weps for the case of graphs. A counter-example to their more general conjecture concerning the extremal number of bounded degree spanning hypergraphs is also given.

Introduction

In extremal graph theory, the central objective is to determine the maximum number of edges a graph with $n$ vertices can possess before it is guaranteed to contain a specific subgraph $H$. This value is known as the extremal number, or Turán number, denoted by $ex(n, H)$. While this value is well-understood for small, fixed subgraphs—such as triangles or small cliques—the problem becomes significantly more complex when $H$ is a spanning graph, meaning it contains all $n$ vertices of the host graph.

The most famous result regarding spanning structures is Ore’s Theorem (1960), which establishes that any graph with $n$ vertices and more than $\binom{n-1}{2} + 1$ edges must contain a Hamiltonian cycle (a cycle visiting every vertex). In this paper, Alon and Yuster provide a definitive generalization of this result, establishing an exact formula for a broad class of sparse spanning graphs and resolving a conjecture by Glebov, Person, and Weps.

The Problem: Spanning Subgraphs and Local Obstructions

When $H$ is a spanning graph, the "bottleneck" that prevents $H$ from appearing in a host graph $G$ is often related to the minimum degree of $H$, denoted $\delta(H)$. If a vertex in $G$ has a degree lower than $\delta(H)$, it cannot possibly serve as the image of any vertex in $H$ under an isomorphism.

The authors sought to determine if the extremal number for any sparse spanning graph follows a predictable pattern based on this minimum degree. Specifically, they investigated whether the formula $ex(n, H) = \binom{n-1}{2} + \delta(H) - 1$ holds whenever $H$ is sufficiently sparse.

Methodology: The Four-Stage Packing Approach

The proof utilizes the concept of graph packing. Rather than searching for $H$ directly within a host graph $G$, the authors attempt to show that $H$ and the complement of $G$ (the set of edges $G$ is missing) can be "packed" onto the same set of vertices without overlapping. If they cannot be packed, then $G$ must contain $H$.

To achieve this, the authors developed a sophisticated four-stage randomized construction to find an embedding of $H$ into $G$:

  1. Stage 1: Initial Matching. The highest-degree vertex of the missing-edge graph is matched with a low-degree vertex in $H$.
  2. Stage 2: Probabilistic Embedding. High-degree vertices are iteratively matched using a probabilistic approach. The authors employ Chernoff bounds to demonstrate that, with high probability, sufficient "available" vertices remain to continue the matching without creating edge overlaps.
  3. Stage 3: Medium-Degree Handling. The remaining medium-degree vertices are embedded.
  4. Stage 4: Completion via Hall’s Marriage Theorem. The final set of low-degree vertices is matched by treating the remaining embedding problem as a perfect matching in a bipartite graph, solved using Hall's Marriage Theorem.

Key Insights

The $\sqrt{n}$ Threshold

A critical discovery in this research is the importance of the maximum degree of $H$, denoted $\Delta(H)$. The authors found that $\Delta(H)$ cannot grow faster than $\sqrt{n}$. If $H$ contains vertices with connections exceeding this order of magnitude, the simple formula for the extremal number fails. The authors provide a specific construction involving cliques to prove that this $\sqrt{n}$ limit is the correct order of magnitude.

Minimum Degree Dominance

For spanning graphs that are sufficiently sparse, the research confirms that the primary obstruction to the existence of $H$ is the vertex in $H$ with the fewest connections. This simplifies the calculation of $ex(n, H)$ to a function of $\delta(H)$.

Hypergraph Divergence

A major contribution of the paper is the demonstration that graph-theoretic logic does not necessarily extend to hypergraphs (where edges connect more than two vertices). The authors disproved a conjecture by Glebov, Person, and Weps regarding hypergraphs by constructing a 3-uniform hypergraph where "local obstructions"—small, dense clusters of vertices—prevent the spanning structure from forming even when the total edge count is very high.

Results and Conclusion

The main theorem states that for a sufficiently large $n$, if $H$ is a graph of order $n$ with no isolated vertices and $\Delta(H) \le \sqrt{n}/200$, then: $$ex(n, H) = \binom{n-1}{2} + \delta(H) - 1$$

This result provides the exact edge count required to guarantee the existence of $H$, generalizing Ore's Theorem and proving the graph-theoretic version of the Glebov-Person-Weps conjecture in a strong form.

Future Directions

While the paper provides a definitive answer for graphs, several questions remain:

  • Optimization of Constants: The constant $1/200$ in the $\sqrt{n}$ bound is likely not optimal and could potentially be improved toward $\sqrt{2}$.
  • Hypergraph Extremal Numbers: Since the previous conjecture for hypergraphs was disproved, the "correct" general formula for spanning hypergraphs remains an open mystery. Future research may focus on identifying the specific "local obstructions" that govern hypergraph extremal numbers.
  • Small $n$ Behavior: The theorem is asymptotic, requiring $n$ to be quite large (estimated at $10^5$). The behavior of these extremal numbers in smaller, real-world networks remains a subject for further study.

Summary updated

Abstract

For a graph $H$, the {\em extremal number} $ex(n,H)$ is the maximum number of edges in a graph of order $n$ not containing a subgraph isomorphic to $H$. Let $δ(H)>0$ and $Δ(H)$ denote the minimum degree and maximum degree of $H$, respectively. We prove that for all $n$ sufficiently large, if $H$ is any graph of order $n$ with $Δ(H) \le \sqrt{n}/200$, then $ex(n,H)={{n-1} \choose 2}+δ(H)-1$. The condition on the maximum degree is tight up to a constant factor. This generalizes a classical result of Ore for the case $H=C_n$, and resolves, in a strong form, a conjecture of Glebov, Person, and Weps for the case of graphs. A counter-example to their more general conjecture concerning the extremal number of bounded degree spanning hypergraphs is also given.
BibTeX
@article{alon2013turan,
  author = {Noga Alon and Raphael Yuster},
  title = {{The Turán number of sparse spanning graphs}},
  journal = {J. Comb. Theory B},
  year = {2013},
  doi = {10.1016/j.jctb.2013.02.002},
}
Figure