Shiksha Nation
Skip to content

Turán graph

  • 4 min read
  • 3 chapters

Explore on Lably

ToursExplore Lably’s 3D tours
(1−1r)n2−s22+(s2).

For r≤7, this edge count can be more succinctly stated as ⌊(1−1r)n22⌋. The graph has s subsets of size q+1, and r−s subsets of size q; each vertex has degree n−q−1 or n−q. It is a regular graph if n is divisible by r (i.e. when s=0).

Turán's theorem

Turán graphs are named after Pál Turán, who used them to prove Turán's theorem, an important result in extremal graph theory.

By the pigeonhole principle, every set of r + 1 vertices in the Turán graph includes two vertices in the same partition subset; therefore, the Turán graph does not contain a clique of size r + 1. According to Turán's theorem, the Turán graph has the maximum possible number of edges among all (r + 1)-clique-free graphs with n vertices. Keevash & Sudakov (2003) show that the Turán graph is also the only (r + 1)-clique-free graph of order n in which every subset of αn vertices spans at least r−13r(2α−1)n2 edges, if α is sufficiently close to 1. The Erdős–Stone theorem extends Turán's theorem by bounding the number of edges in a graph that does not have a fixed Turán graph as a subgraph. Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the chromatic number of the subgraph.

Sign up free to read the rest

2 more chapters are free with a Lably account.

Already have an account?

More in Topics in mathematics