3.3 Erdős-Stone Theorem

The Erdős-Stone theorem is a game-changer in extremal graph theory. It expands on Turán's theorem, giving us a way to estimate the maximum number of edges in graphs without specific subgraphs. This powerful tool helps us understand the structure of large graphs.

By focusing on a graph's chromatic number, the theorem simplifies complex problems. It shows that for any non-bipartite graph, the Turán graph is asymptotically optimal. This insight lets us tackle a wide range of graph theory challenges more effectively.

Erdős-Stone Theorem

Erdős-Stone theorem implications

Top images from around the web for Erdős-Stone theorem implications

• 

  Graph Theory Basics | MA 124 Contemporary Mathematics View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  Graph Theory Basics | MA 124 Contemporary Mathematics View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

1 of 2

Top images from around the web for Erdős-Stone theorem implications

• 

  Graph Theory Basics | MA 124 Contemporary Mathematics View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  Graph Theory Basics | MA 124 Contemporary Mathematics View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

1 of 2

• Fundamental result in extremal graph theory that generalizes Turán's theorem
• Provides an asymptotic estimate for the maximum number of edges in a graph that does not contain a given complete r-partite subgraph
• Statement: For any fixed graph H with chromatic number $\chi(H) = r \geq 2$, the maximum number of edges in an n-vertex graph that does not contain H as a subgraph is asymptotically equal to the number of edges in the complete (r-1)-partite graph with n vertices and nearly equal part sizes
  • In other words, $[ex(n, H)](https://www.fiveableKeyTerm:ex(n,_h)) = (1 - \frac{1}{r-1} + o(1))\binom{n}{2}$, where $ex(n, H)$ is the maximum number of edges in an n-vertex H-free graph
• Provides a tight asymptotic bound for the Turán number of any non-bipartite graph
• Shows that the complete (r-1)-partite graph with nearly equal part sizes is asymptotically extremal for any graph with chromatic number r
• Can be used to determine the asymptotic behavior of the Turán number for a wide range of graphs (cycles, complete bipartite graphs)

Erdős-Stone vs Turán theorems

• Turán's theorem is a special case of the Erdős-Stone theorem when the forbidden subgraph is a complete graph
  • States that the maximum number of edges in an n-vertex graph that does not contain a complete graph $K_r$ as a subgraph is achieved by the complete (r-1)-partite graph with nearly equal part sizes, denoted as the Turán graph $T(n, r-1)$
  • The number of edges in the Turán graph is given by $|E(T(n, r-1))| = (1 - \frac{1}{r-1} + o(1))\binom{n}{2}$
• Erdős-Stone theorem generalizes Turán's theorem by considering any graph H with chromatic number $\chi(H) = r$ instead of just complete graphs
• Shows that the asymptotic behavior of the Turán number for any graph H depends only on its chromatic number, not its specific structure

Asymptotic behavior of Turán numbers

To determine the asymptotic behavior of the Turán number for a graph H using the Erdős-Stone theorem:

1. Determine the chromatic number $\chi(H)$ of the graph H
2. Apply the Erdős-Stone theorem with $r = \chi(H)$ to obtain the asymptotic estimate $ex(n, H) = (1 - \frac{1}{r-1} + o(1))\binom{n}{2}$

Example: Consider the cycle graph $C_5$ (a pentagon)

• The chromatic number of $C_5$ is $\chi(C_5) = 3$
• By the Erdős-Stone theorem, $ex(n, C_5) = (1 - \frac{1}{3-1} + o(1))\binom{n}{2} = (\frac{1}{2} + o(1))\binom{n}{2}$
• This means that the maximum number of edges in an n-vertex graph without a $C_5$ subgraph is asymptotically half the total number of possible edges

Density of graphs with forbidden subgraphs

• Erdős-Stone theorem can be used to calculate the asymptotic edge density of graphs that do not contain a specific subgraph
  • Edge density of a graph G is defined as $d(G) = \frac{|E(G)|}{\binom{n}{2}}$, where $|E(G)|$ is the number of edges and n is the number of vertices
• To find the asymptotic edge density of H-free graphs using the Erdős-Stone theorem:
  1. Determine the chromatic number $\chi(H)$ of the forbidden subgraph H
  2. Apply the Erdős-Stone theorem to obtain the asymptotic estimate for the maximum number of edges in an H-free graph: $ex(n, H) = (1 - \frac{1}{r-1} + o(1))\binom{n}{2}$, where $r = \chi(H)$
  3. The asymptotic edge density of H-free graphs is given by $d(H) = 1 - \frac{1}{r-1}$

Example: Determine the asymptotic edge density of graphs that do not contain a complete bipartite graph $K_{3,3}$ as a subgraph

• The chromatic number of $K_{3,3}$ is $\chi(K_{3,3}) = 2$
• By the Erdős-Stone theorem, the asymptotic edge density of $K_{3,3}$-free graphs is $d(K_{3,3}) = 1 - \frac{1}{2-1} = 0$
• This means that as the number of vertices grows, the edge density of $K_{3,3}$-free graphs approaches 0