Editing Turán's theorem

{{Short description|Extremal graph theory bound on clique-free graph edges}}
{{distinguish|text=[[Turán's method]] in analytic number theory}}
In [[graph theory]], '''Turán's theorem''' bounds the number of edges that can be included in an [[undirected graph]] that does not have a [[clique (graph theory)|complete subgraph]] of a given size. It is one of the central results of [[extremal graph theory]], an area studying the largest or smallest graphs with given properties, and is a special case of the [[forbidden subgraph problem]] on the maximum number of edges in a graph that does not have a given subgraph.

An example of an <math>n</math>-[[vertex (graph theory)|vertex]] graph that does not contain any <math>(r+1)</math>-vertex clique <math>K_{r+1}</math> may be formed by partitioning the set of <math>n</math> vertices into <math>r</math> parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the [[Turán graph]] <math>T(n,r)</math>. Turán's theorem states that the Turán graph has the largest number of edges among all {{math|''K''<sub>''r''+1</sub>}}-free {{mvar|n}}-vertex graphs.

Turán's theorem, and the [[Turán graph]]s giving its extreme case, were first described and studied by [[Hungary|Hungarian]] mathematician [[Pál Turán]] in 1941.{{r|turan}} The [[special case]] of the theorem for [[triangle-free graph]]s is known as '''Mantel's theorem'''; it was stated in 1907 by Willem Mantel, a Dutch mathematician.{{r|mantel}}

==Statement==
Turán's theorem states that every graph <math>G</math> with <math>n</math> vertices that does not contain <math>K_{r+1}</math> as a subgraph has at most as many edges as the Turán graph <math>T(n,r)</math>. For a fixed value of <math>r</math>, this graph has<math display="block">\left(1-\frac{1}{r}+o(1)\right) \frac{n^2}{2}</math>edges, using [[Little o notation|little-o notation]]. Intuitively, this means that as <math>n</math> gets larger, the fraction of edges included in <math>T(n,r)</math> gets closer and closer to <math>1-\frac{1}{r}</math>. Many of the following proofs only give the upper bound of <math>\left(1-\frac{1}{r}\right)\frac{n^2}{2}</math>.{{r|az}}

==Proofs==
{{harvtxt|Aigner|Ziegler|2018}} list five different proofs of Turán's theorem.{{r|az}}
Many of the proofs involve reducing to the case where the graph is a complete [[multipartite graph]], and showing that the number of edges is maximized when there are <math>r</math> parts of size as close as possible to equal.

=== Induction ===
[[File:Turán-Induct-r=3.png|thumb|256x256px|(Induction on n) An example of sets <math>A</math> and <math>B</math> for <math>r=3</math>.]]
[[File:Turán-Erdős-Replacement.png|thumb|299x299px|(Maximal Degree Vertex) Deleting edges within <math>A</math> and drawing edges between <math>A</math> and <math>B</math>.]]
This was Turán's original proof. Take a <math>K_{r+1}</math>-free graph on <math>n</math> vertices with the maximal number of edges. Find a <math>K_r</math> (which exists by maximality), and partition the vertices into the set <math>A</math> of the <math>r</math> vertices in the <math>K_r</math> and the set <math>B</math> of the <math>n-r</math> other vertices.

Now, one can bound edges above as follows:

* There are exactly <math>\binom{r}{2}</math> edges within <math>A</math>.
* There are at most <math>(r-1)|B|=(r-1)(n-r)</math> edges between <math>A</math> and <math>B</math>, since no vertex in <math>B</math> can connect to all of <math>A</math>.
* The number of edges within <math>B</math> is at most the number of edges of <math>T(n-r,r)</math> by the inductive hypothesis.

Adding these bounds gives the result.{{r|turan|az}}

=== Maximal Degree Vertex ===
This proof is due to [[Paul Erdős]]. Take the vertex <math>v</math> of largest degree. Consider the set <math>A</math> of vertices not adjacent to <math>v</math> and the set <math>B</math> of vertices adjacent to <math>v</math>.

Now, delete all edges within <math>A</math> and draw all edges between <math>A</math> and <math>B</math>. This increases the number of edges by our maximality assumption and keeps the graph <math>K_{r+1}</math>-free. Now, <math>B</math> is <math>K_r</math>-free, so the same argument can be repeated on <math>B</math>.

Repeating this argument eventually produces a graph in the same form as a [[Turán graph]], which is a collection of independent sets, with edges between each two vertices from different independent sets. A simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible.{{r|az|erdos}}

=== Complete Multipartite Optimization ===
This proof, as well as the Zykov Symmetrization proof, involve reducing to the case where the graph is a complete [[multipartite graph]], and showing that the number of edges is maximized when there are <math>r</math> independent sets of size as close as possible to equal. This step can be done as follows:

Let <math>S_1, S_2, \ldots, S_r</math> be the independent sets of the multipartite graph. Since two vertices have an edge between them if and only if they are not in the same independent set, the number of edges is

<math display="block">\sum_{i \neq j} \left|S_i\right|\left|S_j\right|=\frac{1}{2}\left(n^2-\sum_{i} \left|S_i\right|^2\right),</math>

where the left hand side follows from direct counting, and the right hand side follows from complementary counting. To show the <math>\left(1-\frac{1}{r}\right)\frac{n^2}{2}</math> bound, applying the [[Cauchy–Schwarz inequality]] to the <math display="inline">\sum\limits_i\left|S_i\right|^2</math> term on the right hand side suffices, since <math display="inline">\sum\limits_i\left|S_i\right|=n</math>.

To prove the Turán Graph is optimal, one can argue that no two <math>S_i</math> differ by more than one in size. In particular, supposing that we have <math>\left|S_i\right| \geq \left|S_j\right|+2</math> for some <math>i \neq j</math>, moving one vertex from <math>S_j</math> to <math>S_i</math> (and adjusting edges accordingly) would increase the value of the sum. This can be seen by examining the changes to either side of the above expression for the number of edges, or by noting that the degree of the moved vertex increases.

=== Lagrangian ===
This proof is due to {{harvtxt|Motzkin|Straus|1965}}. They begin by considering a <math>K_{r+1}</math> free graph with vertices labelled <math>1,2,\ldots,n</math>, and considering maximizing the function<math display="block">f(x_1,x_2,\ldots,x_n)=\sum_{i,j\ \text{adjacent}} x_ix_j</math>over all nonnegative <math>x_1,x_2,\ldots,x_n</math> with sum <math>1</math>. This function is known as the [[Homomorphism density#Lagrangian|Lagrangian]] of the graph and its edges.

The idea behind their proof is that if <math>x_i,x_j</math> are both nonzero while <math>i,j</math> are not adjacent in the graph, the function<math display="block">f(x_1,\ldots,x_i-t,\ldots,x_j+t,\ldots,x_n)</math>is linear in <math>t</math>. Hence, one can either replace <math>(x_i,x_j)</math> with either <math>(x_i+x_j,0)</math> or <math>(0,x_i+x_j)</math> without decreasing the value of the function. Hence, there is a point with at most <math>r</math> nonzero variables where the function is maximized.


Now, the [[Cauchy–Schwarz inequality]] gives that the maximal value is at most  <math>\frac{1}{2}\left(1-\frac{1}{r}\right)</math>. Plugging in <math>x_i=\frac{1}{n}</math> for all <math>i</math> gives that the maximal value is at least <math>\frac{|E|}{n^2}</math>, giving the desired bound.{{r|az|ms}}

=== Probabilistic Method ===
The key claim in this proof was independently found by Caro and Wei. This proof is due to [[Noga Alon]] and [[Joel Spencer]], from their book ''The Probabilistic Method''. The proof shows that every graph with degrees <math>d_1,d_2,\ldots,d_n</math> has an [[Independent set (graph theory)|independent set]] of size at least<math display="block">S=\frac{1}{d_1+1}+\frac{1}{d_2+1}+\cdots+\frac{1}{d_n+1}.</math>The proof attempts to find such an independent set as follows:
* Consider a [[random permutation]] of the vertices of a <math>K_{r+1}</math>-free graph
* Select every vertex that is adjacent to none of the vertices before it.

A vertex of degree <math>d</math> is included in this with probability <math>\frac{1}{d+1}</math>, so this process gives an average of <math>S</math> vertices in the chosen set.
[[File:Turán-Zykov-Step-1.png|thumb|375x375px|(Zykov Symmetrization) Example of first step.]]
Applying this fact to the [[complement graph]] and bounding the size of the chosen set using the Cauchy–Schwarz inequality proves Turán's theorem.{{r|az}} See {{slink|Method_of_conditional_probabilities|Turán's_theorem}} for more.
[[File:Turán-Zykov-Step-2.png|thumb|375x375px|(Zykov Symmetrization) Example of second step.]]

=== Zykov Symmetrization ===
Aigner and Ziegler call the final one of their five proofs "the most beautiful of them all". Its origins are unclear, but the approach is often referred to as Zykov Symmetrization as it was used in Zykov's proof of a generalization of Turán's Theorem {{r|zykov}}. This proof goes by taking a <math>K_{r+1}</math>-free graph, and applying steps to make it more similar to the Turán Graph while increasing edge count.

In particular, given a <math>K_{r+1}</math>-free graph, the following steps are applied:

* If <math>u,v</math> are non-adjacent vertices and <math>u</math> has a higher degree than <math>v</math>, replace <math>v</math> with a copy of <math>u</math>. Repeat this until all non-adjacent vertices have the same degree.
* If <math>u,v,w</math> are vertices with <math>u,v</math> and <math>v,w
</math> non-adjacent but <math>u,w</math> adjacent, then replace both <math>u</math> and <math>w
</math> with copies of <math>v
</math>.

All of these steps keep the graph <math>K_{r+1}</math> free while increasing the number of edges.

Now, non-adjacency forms an [[equivalence relation]]. The [[equivalence class]]es give that any maximal graph the same form as a Turán graph. As in the maximal degree vertex proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible.{{r|az}}

==Mantel's theorem==
The special case of Turán's theorem for <math>r=2</math> is Mantel's theorem: The maximum number of edges in an <math>n</math>-vertex [[triangle-free graph]] is <math>\lfloor n^2/4 \rfloor.</math>{{r|mantel}} In other words, one must delete nearly half of the edges in <math>K_n</math> to obtain a triangle-free graph.

A strengthened form of Mantel's theorem states that any Hamiltonian graph with at least <math>n^2/4</math> edges must either be the [[complete bipartite graph]] <math>K_{n/2,n/2}</math> or it must be [[pancyclic graph|pancyclic]]: not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices in the graph.{{r|bondy}}

Another strengthening of Mantel's theorem states that the edges of every <math>n</math>-vertex graph may be covered by at most <math>\lfloor n^2/4 \rfloor</math> [[clique (graph theory)|cliques]] which are either edges or triangles. As a corollary, the graph's [[Intersection number (graph theory)|intersection number]] (the minimum number of cliques needed to cover all its edges) is at most <math>\lfloor n^2/4 \rfloor</math>.{{r|egp}}

==Hypergraphs and the Turán density==

There is no analogous of Turán's theorem for <math>k</math>-uniform hypergraphs. In fact, in Turán's original paper{{r|turan}}, he asked for the maximum number of hyperedges an <math>n</math>-vertex <math>3</math>-uniform hypergraph can have without containing the complete <math>3</math>-uniform hypergraph on <math>4</math> vertices, <math>K_4^{(3)}</math>. This maximum number of hyperedges is known as the ''extremal number''. More precisely and more generally, for a hypergraph <math>F</math>, the '''extremal number''' of <math>F</math> for <math>n</math> vertices, ex<math>(n,F)</math>, is the maximum number of hyperedges an <math>n</math>-vertex <math>k</math>-uniform hypergraph can have without containing a copy of <math>F</math>. To obtain a cleaner parameter, the '''Turán density''' of <math>F</math> is defined by the following limit
<math display="block">
\pi(F) = \lim_{n\to \infty}\frac{\text{ex}(n,F)}{\binom{n}{k}}.</math>
It is easy to see that <math>\text{ex}(n,F)/\tbinom{n}{k}</math> is non increasing sequence, and therefore, the limit above always converges. 
With this definition, an approximate answer for Turán's question would determine <math>\pi(K_4^{(3)})</math>.

== 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}}.

== See also ==
* [[Erdős–Stone theorem]], a generalization of Turán's theorem from forbidden cliques to forbidden Turán graphs

==References==
{{reflist|refs=

<ref name=az>{{citation
 | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
 | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
 | contribution = Chapter 41: Turán’s graph theorem
 | doi = 10.1007/978-3-662-57265-8_41
 | edition = 6th
 | isbn = 978-3-662-57265-8
 | pages = 285–289
 | publisher = Springer-Verlag
 | title = Proofs from THE BOOK
 | title-link = Proofs from THE BOOK
 | year = 2018}}</ref>

<ref name=bondy>{{citation
 | last = Bondy | first = J. A. | authorlink = John Adrian Bondy
 | doi = 10.1016/0095-8956(71)90016-5
 | issue = 1
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 80–84
 | title = Pancyclic graphs I
 | volume = 11
 | year = 1971| doi-access = 
 }}</ref>

<ref name=erdos>{{citation
 | last = Erdős | first = Pál | authorlink = Paul Erdős
 | journal = Matematikai Lapok
 | language = Hungarian
 | mr = 307975
 | pages = 249–251
 | title = Turán Pál gráf tételéről
 | trans-title = On the graph theorem of Turán
 | url = https://users.renyi.hu/~p_erdos/1971-27.pdf
 | volume = 21
 | year = 1970}}</ref>

<ref name=egp>{{citation | last1 = Erdős | first1 = Paul | authorlink1 = Paul Erdős | last2 = Goodman | first2 = A. W. | authorlink2 = Adolph Winkler Goodman | last3 = Pósa | first3 = Louis | authorlink3 = Lajos Pósa (mathematician) | title = The representation of a graph by set intersections | url = http://www.renyi.hu/~p_erdos/1966-21.pdf | journal = Canadian Journal of Mathematics | volume = 18 | issue = 1 | year = 1966 | pages = 106–112 | mr = 0186575 | doi = 10.4153/CJM-1966-014-3 | s2cid = 646660 | access-date = 2011-03-05 | archive-date = 2021-04-16 | archive-url = https://web.archive.org/web/20210416163126/https://www.renyi.hu/~p_erdos/1966-21.pdf | url-status = live }}</ref>

<ref name=mantel>{{citation
 | last = Mantel | first = W.
 | journal = Wiskundige Opgaven
 | pages = 60–61
 | title = Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)
 | volume = 10
 | year = 1907}}</ref>

<ref name=ms>{{citation
 | last1 = Motzkin | first1 = T. S. | author1-link = Theodore Motzkin
 | last2 = Straus | first2 = E. G. | author2-link = Ernst G. Straus
 | doi = 10.4153/CJM-1965-053-6
 | journal = [[Canadian Journal of Mathematics]]
 | mr = 175813
 | pages = 533–540
 | title = Maxima for graphs and a new proof of a theorem of Turán
 | volume = 17
 | year = 1965| s2cid = 121387797 | doi-access = free
 }}</ref>

<ref name=turan>{{Citation
 | last = Turán
 | first = Paul | authorlink = Pál Turán
 | year = 1941
 | title = On an extremal problem in graph theory
 | journal = Matematikai és Fizikai Lapok
 | volume = 48
 | pages = 436–452
 | language = Hungarian}}</ref>

<ref name=zykov>{{Citation
 | last = Zykov
 | first = A.
 | year = 1949
 | title = On some properties of linear complexes
 | journal = Mat. Sb. |series=New Series
 | volume = 24
 | pages = 163–188
 | language = Russian}}</ref>

<ref name=alonshik>{{citation
 | last1 = Alon | first1 = Noga
 | last2 = Shikhelman | first2 = Clara
 | doi = 10.1016/j.jctb.2016.03.004
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 146–172
 | title = Many T copies in H-free graphs
 | volume = 121
 | year = 2016| s2cid = 5552776
 | doi-access = free
 | arxiv = 1409.4192
 }}</ref>

<ref name=raz>{{Cite journal|last=Razborov|first=Alexander|date=2008|title=On the minimal density of triangles in graphs.|url=http://people.cs.uchicago.edu/~razborov/files/triangles.pdf|journal=Combinatorics, Probability and Computing|volume=17|issue=4|pages=603–618|doi=10.1017/S0963548308009085|s2cid=26524353|via=MathSciNet (AMS)|archive-date=2021-11-30|access-date=2021-11-28|archive-url=https://web.archive.org/web/20211130062334/http://people.cs.uchicago.edu/~razborov/files/triangles.pdf|url-status=live}}</ref>


<ref name=reiher>{{citation
 | last = Reiher | first = Christian
 | doi = 10.4007/annals.2016.184.3.1
 | journal = Annals of Mathematics
 | pages = 683–707
 | title = The clique density theorem
 | volume = 184
 | year = 2016| issue = 3
 | arxiv = 1212.2454
 | s2cid = 59321123
 }}</ref>


<ref name=largenetworks>{{citation
 | last = Lovász | first = László
 | title = Large networks and graph limits}}</ref>

}}

{{DEFAULTSORT:Turans theorem}}
[[Category:Extremal graph theory]]
[[Category:Theorems in graph theory]]
[[Category:Articles containing proofs]]