Editing Turán's theorem (section)

== Generalizations ==

=== Other Forbidden Subgraphs ===
Turán's theorem shows that the largest number of edges in a <math>K_{r+1}</math>-free graph is <math>\left(1-\frac{1}{r}+o(1)\right) \frac{n^2}{2}</math>. The [[Erdős–Stone theorem]] finds the number of edges up to a <math>o(n^2)</math> error in all other graphs:<blockquote>(Erdős–Stone) Suppose <math>H</math> is a graph with [[chromatic number]] <math>\chi(H)</math>. The largest possible number of edges in a graph where <math>H</math> does not appear as a subgraph is<math display="block">\left(1-\frac{1}{\chi(H)-1}+o(1)\right) \frac{n^2}{2}</math>where the <math>o(1)</math> constant only depends on <math>H</math>. </blockquote>One can see that the Turán graph <math>T(n,\chi(H)-1)</math> cannot contain any copies of <math>H</math>, so the Turán graph establishes the lower bound. As a <math>K_{r+1}</math> has chromatic number <math>r+1</math>, Turán's theorem is the special case in which <math>H</math> is a <math>K_{r+1}</math>.

The general question of how many edges can be included in a graph without a copy of some <math>H</math> is the [[forbidden subgraph problem]].

=== Maximizing Other Quantities ===
Another natural extension of Turán's theorem is the following question: if a graph has no <math>K_{r+1}</math>s, how many copies of <math>K_{a}</math> can it have? Turán's theorem is the case where <math>a=2</math>. Zykov's Theorem answers this question:<blockquote>(Zykov's Theorem) The graph on <math>n</math> vertices with no <math>K_{r+1}</math>s and the largest possible number of <math>K_{a}</math>s is the Turán graph <math>T(n,r)</math></blockquote>This was first shown by Zykov (1949) using Zykov Symmetrization{{r|turan|az}}. Since the Turán Graph contains <math>r</math> parts with size around <math>\frac{n}{r}</math>, the number of <math>K_{a}</math>s in <math>T(n,r)</math> is around <math>\binom{r}{a}\left(\frac{n}{r}\right)^a</math>.

A paper by Alon and Shikhelman in 2016 gives the following generalization, which is similar to the Erdos-Stone generalization of Turán's theorem:<blockquote>(Alon-Shikhelman, 2016) Let <math>H</math> be a graph with chromatic number <math>\chi(H)>a</math>. The largest possible number of <math>K_{a}</math>s in a graph with no copy of <math>H</math> is

<math>(1+o(1))\binom{\chi(H)-1}{a}\left(\frac{n}{\chi(H)-1}\right)^a.</math>{{r|alonshik}}</blockquote>As in Erdős–Stone, the Turán graph <math>T(n,\chi(H)-1)</math> attains the desired number of copies of <math>K_{a}</math>.

=== Edge-Clique region ===
Turan's theorem states that if a graph has edge [[homomorphism density]] strictly above <math>1-\frac{1}{r-1}</math>, it has a nonzero number of <math>K_r</math>s. One could ask the far more general question: if you are given the edge density of a graph, what can you say about the density of <math>K_r</math>s?

An issue with answering this question is that for a given density, there may be some bound not attained by any graph, but approached by some infinite sequence of graphs. To deal with this, [[Weighted graph|weighted graphs]] or [[graphon]]s are often considered. In particular, graphons contain the limit of any infinite sequence of graphs.

For a given edge density <math>d</math>, the construction for the largest <math>K_r</math> density is as follows:<blockquote>Take a number of vertices <math>N</math> approaching infinity. Pick a set of <math>\sqrt{d}N</math> of the vertices, and connect two vertices if and only if they are in the chosen set.</blockquote>This gives a <math>K_r</math> density of <math>d^{k/2}.</math> The construction for the smallest <math>K_r</math> density is as follows:<blockquote>Take a number of vertices approaching infinity. Let <math>t</math> be the integer such that <math>1-\frac{1}{t-1} < d \leq 1-\frac{1}{t}</math>. Take a <math>t</math>-partite graph where all parts but the unique smallest part have the same size, and sizes of the parts are chosen such that the total edge density is <math>d</math>.</blockquote>For <math>d\leq 1-\frac{1}{r-1}</math>, this gives a graph that is <math>(r-1)</math>-partite and hence gives no <math>K_r</math>s.

The lower bound was proven by Razborov (2008){{r|raz}} for the case of triangles, and was later generalized to all cliques by Reiher (2016){{r|reiher}}. The upper bound is a consequence of the Kruskal–Katona theorem {{r|largenetworks}}.