13.2 Turán's theorem and extremal graphs

Turán's theorem is a key result in extremal graph theory. It establishes the maximum number of edges a graph can have without containing certain complete subgraphs, linking edge density to structural properties.

This theorem forms the basis for many other results in the field. It introduces important concepts like clique number, edge density, and Turán graphs, which are crucial for understanding graph structure and properties.

Turán's Theorem and Extremal Graph Theory

Turán's theorem in graph theory

Top images from around the web for Turán's theorem in graph theory

• 

  Line graph - Wikipedia View original

  Is this image relevant?

• 

  Clique (graph theory) - Wikipedia View original

  Is this image relevant?

• 

  Line graph - Wikipedia View original

  Is this image relevant?

• 

  Clique (graph theory) - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Turán's theorem in graph theory

• 

  Line graph - Wikipedia View original

  Is this image relevant?

• 

  Clique (graph theory) - Wikipedia View original

  Is this image relevant?

• 

  Line graph - Wikipedia View original

  Is this image relevant?

• 

  Clique (graph theory) - Wikipedia View original

  Is this image relevant?

1 of 2

• Turán's theorem fundamental result in extremal graph theory provides upper bound on edge count in graphs without complete subgraphs
• Extremal graph theory studies maximum or minimum graphs satisfying certain properties focuses on relationships between graph parameters and structural properties
• Turán's theorem establishes connection between edge density and presence of complete subgraphs serves as foundation for many other results in extremal graph theory
• Key concepts include clique number (size of largest complete subgraph), edge density (ratio of edges to maximum possible edges), and Turán graph (extremal graph achieving maximum edges without containing specific complete subgraph)

Maximum edges without subgraphs

• Turán's theorem states for graph G with n vertices and no $K_{r+1}$ subgraph, maximum number of edges is $e(G) \leq \frac{r-1}{2r} n^2$
• Applies to triangle-free graphs (r = 2): $e(G) \leq \frac{n^2}{4}$ and $K_4$-free graphs (r = 3): $e(G) \leq \frac{n^2}{3}$
• Erdős-Stone-Simonovits theorem generalizes Turán's result to forbidden subgraphs other than complete graphs
• Techniques for determining maximum edges include induction on vertex count, averaging arguments, and extremal graph constructions

Properties of Turán graphs

• Turán graph complete r-partite graph with n vertices divided as equally as possible
• Construction process:

1. Divide n vertices into r parts
2. Connect all vertices between different parts
3. Ensure size difference between parts is at most 1

• Properties include maximality (contains maximum edges without $K_{r+1}$ subgraph), symmetry (vertex-transitive), and degree distribution (vertices have degree $\frac{r-1}{r}n$ or $\frac{r-1}{r}n - 1$)
• Examples include T(n,2) (complete bipartite graph with parts of size $\lfloor \frac{n}{2} \rfloor$ and $\lceil \frac{n}{2} \rceil$) and T(n,3) (complete tripartite graph with parts differing by at most 1 in size)

Applications of Turán's theorem

• Problem-solving strategies involve identifying forbidden subgraph, applying Turán's theorem for edge upper bound, and constructing extremal graph to show bound tightness
• Extensions include generalized Turán problems (forbidding multiple subgraphs), Turán-type problems for hypergraphs, and spectral Turán theorems (using eigenvalues to bound subgraph occurrences)
• Applications to other areas include Ramsey theory (connections between Turán's theorem and Ramsey numbers) and probabilistic method (using Turán's theorem to prove existence of certain graphs)
• Advanced techniques involve stability results (characterizing graphs close to extremal), supersaturation (counting forbidden subgraphs in dense graphs), and flag algebras (computer-assisted proofs in extremal graph theory)