In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, Turán's theorem bounds the number of edges that can be included in an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
that does not have a
complete subgraph of a given size. It is one of the central results of
extremal graph theory
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local ...
, an area studying the largest or smallest graphs with given properties, and is a special case of the
forbidden subgraph problem In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges \operatorname(n,G) an n-vertex graph can have such that it does not have a Glossary of graph theory#Subgraphs, subgr ...
on the maximum number of edges in a graph that does not have a given subgraph.
An example of an
-
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
graph that does not contain any
-vertex clique
may be formed by partitioning the set of
vertices into
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
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to dif ...
. Turán's theorem states that the Turán graph has the largest number of edges among all -free -vertex graphs.
Turán's theorem, and the
Turán graph
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to dif ...
s giving its extreme case, were first described and studied by
Hungarian mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Pál Turán
Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. He had a long collaboration with fellow Hungarian mathematician Paul Erdős, lasting 4 ...
in 1941. The
special case
In logic, especially as applied in mathematics, concept is a special case or specialization of concept precisely if every instance of is also an instance of but not vice versa, or equivalently, if is a generalization of . A limiting case is ...
of the theorem for
triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
s is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician.
Statement
Turán's theorem states that every graph
with
vertices that does not contain
as a subgraph has at most as many edges as the Turán graph
. For a fixed value of
, this graph has
edges, using
Little-o Notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
. Intuitively, this means that as
gets larger, the fraction of edges included in
gets closer and closer to
. Many of the following proofs only give the upper bound of
.
Proofs
list five different proofs of Turán's theorem.
Many of the proofs involve reducing to the case where the graph is a complete
multipartite graph
In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge h ...
, and showing that the number of edges is maximized when there are
parts of size as close as possible to equal. This step can be done
Induction
![Turán-Erdős-Replacement](https://upload.wikimedia.org/wikipedia/commons/0/0b/Tur%C3%A1n-Erd%C5%91s-Replacement.png)
This was Turán's original proof. Take a
-free graph on
vertices with the maximal number of edges. Find a
(which exists by maximality), and partition the vertices into the set
of the
vertices in the
and the set
of the
other vertices.
Now, one can bound edges above as follows:
* There are exactly
edges within
.
* There are at most
edges between
and
, since no vertex in
can connect to all of
.
* The number of edges within
is at most the number of edges of
by the inductive hypothesis.
Adding these bounds gives the result.
Maximal Degree Vertex
This proof is due to
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
. Take the vertex
of largest degree. Consider the set
of vertices not adjacent to
and the set
of vertices adjacent to
.
Now, delete all edges within
and draw all edges between
and
. This increases the number of vertices by our maximality assumption and keeps the graph
-free. Now,
is
-free, so the same argument can be repeated on
.
Repeating this argument eventually produces a graph in the same form as a
Turán graph
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to dif ...
, 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.
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
In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge h ...
, and showing that the number of edges is maximized when there are
independent sets of size as close as possible to equal. This step can be done as follows:
Let
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
where the left hand side follows from direct counting, and the right hand side follows from complementary counting. To show the
bound, applying the
Cauchy–Schwarz inequality
The Cauchy–Schwarz inequality (also called Cauchy–Bunyakovsky–Schwarz inequality) is considered one of the most important and widely used inequalities in mathematics.
The inequality for sums was published by . The corresponding inequality fo ...
to the
term on the right hand side suffices, since
.
To prove the Turán Graph is optimal, one can argue that no two
differ by more than one in size. In particular, supposing that we have
for some
, moving one vertex from
to
(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 . They begin by considering a
free graph with vertices labelled
, and considering maximizing the function
over all nonnegative
with sum
. This function is known as the
Lagrangian
Lagrangian may refer to:
Mathematics
* Lagrangian function, used to solve constrained minimization problems in optimization theory; see Lagrange multiplier
** Lagrangian relaxation, the method of approximating a difficult constrained problem with ...
of the graph and its edges.
The idea behind their proof is that if
are both nonzero while
are not adjacent in the graph, the function
is linear in
. Hence, one can either replace
with either
or
without decreasing the value of the function. Hence, there is a point with at most
nonzero variables where the function is maximized.
Now, the
Cauchy–Schwarz inequality
The Cauchy–Schwarz inequality (also called Cauchy–Bunyakovsky–Schwarz inequality) is considered one of the most important and widely used inequalities in mathematics.
The inequality for sums was published by . The corresponding inequality fo ...
gives that the maximal value is at most
. Plugging in
for all
gives that the maximal value is at least
, giving the desired bound.
Probabilistic Method
The key claim in this proof was independently found by Caro and Wei. This proof is due to
Noga Alon
Noga Alon ( he, נוגה אלון; born 17 February 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of ...
and
Joel Spencer
Joel Spencer (born April 20, 1946) is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervi ...
, from their book ''The Probabilistic Method''. The proof shows that every graph with degrees
has an
independent set of size at least
The proof attempts to find such an independent set as follows:
* Consider a
random permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...
of the vertices of a
-free graph
* Select every vertex that is adjacent to none of the vertices before it.
A vertex of degree
is included in this with probability
, so this process gives an average of
vertices in the chosen set.
![Turán-Zykov-Step-1](https://upload.wikimedia.org/wikipedia/commons/9/92/Tur%C3%A1n-Zykov-Step-1.png)
Applying this fact to the
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...
and bounding the size of the chosen set using the Cauchy–Schwarz inequality proves Turán's theorem. See for more.
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 . This proof goes by taking a
-free graph, and applying steps to make it more similar to the Turán Graph while increasing edge count.
In particular, given a
-free graph, the following steps are applied:
* If
are non-adjacent vertices and
has a higher degree than
, replace
with a copy of
. Repeat this until all non-adjacent vertices have the same degree.
* If
are vertices with
and
non-adjacent but
adjacent, then replace both
and
with copies of
.
All of these steps keep the graph
free while increasing the number of edges.
Now, non-adjacency forms an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
. The
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
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.
Mantel's theorem
The special case of Turán's theorem for
is Mantel's theorem: The maximum number of edges in an
-vertex
triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
is
In other words, one must delete nearly half of the edges in
to obtain a triangle-free graph.
A strengthened form of Mantel's theorem states that any Hamiltonian graph with at least
edges must either be the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
or it must be
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.
Another strengthening of Mantel's theorem states that the edges of every
-vertex graph may be covered by at most
cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
which are either edges or triangles. As a corollary, the graph's
intersection number
In mathematics, and especially in algebraic geometry, the intersection number generalizes the intuitive notion of counting the number of times two curves intersect to higher dimensions, multiple (more than 2) curves, and accounting properly for ta ...
(the minimum number of cliques needed to cover all its edges) is at most
.
Generalizations
Other Forbidden Subgraphs
Turán's theorem shows that the largest number of edges in a
-free graph is
. The
Erdős–Stone theorem
In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an ''H''-free graph for a non-complete graph ''H''. It is named after Paul Erdős and Arthur Stone, who pr ...
finds the number of edges up to a
error in all other graphs:
(Erdős–Stone) Suppose is a graph with chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
. The largest possible number of edges in a graph with no subgraph of iswhere the constant only depends on .
One can see that the Turán graph
cannot contain any copies of
, so the Turán graph establishes the lower bound. As a
has chromatic number
, Turán's theorem is the special case in which
is a
.
The general question of how many edges can be included in a graph without a copy of some
is the
forbidden subgraph problem In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges \operatorname(n,G) an n-vertex graph can have such that it does not have a Glossary of graph theory#Subgraphs, subgr ...
.
Maximizing Other Quantities
Another natural extension of Turán's theorem is the following question: if a graph has no
s, how many copies of
can it have? Turán's theorem is the case where
. Zykov's Theorem answers this question:
(Zykov's Theorem) The graph on vertices with no s and the largest possible number of s is the Turán graph
This was first shown by Zykov (1949) using Zykov Symmetrization. Since the Turán Graph contains
parts with size around
, the number of
s in
is around
.
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:
(Alon-Shikhelman, 2016) Let be a graph with chromatic number . The largest possible number of s in a graph with no copy of is
As in Erdős–Stone, the Turán graph
attains the desired number of copies of
.
Edge-Clique region
Turan's theorem states that if a graph has edge
homomorphism density
In the mathematical field of extremal graph theory, homomorphism density with respect to a graph H is a parameter t(H,-) that is associated to each graph G in the following manner:
: t(H,G):=\frac.
Above, \operatorname(H,G) is the set of graph h ...
strictly above
, it has a nonzero number of
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
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 graphs
A weight function is a mathematical device used when performing a sum, integral, or average to give some elements more "weight" or influence on the result than other elements in the same set. The result of this application of a weight function is ...
or
graphon
GraphOn GO-Global is a multi-user remote access application for Windows.
Overview
GO-Global allows multiple users to concurrently run Microsoft Windows applications installed on a Windows server or server farm from network-connected lo ...
s are often considered. In particular, graphons contain the limit of any infinite sequence of graphs.
For a given edge density
, the construction for the largest
density is as follows:
Take a number of vertices approaching infinity. Pick a set of of the vertices, and connect two vertices if and only if they are in the chosen set.
This gives a
density of
The construction for the smallest
density is as follows:
Take a number of vertices approaching infinity. Let be the integer such that . Take a -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 .
For
, this gives a graph that is
-partite and hence gives no
s.
The lower bound was proven by Razborov (2008) for the case of triangles, and was later generalized to all cliques by Reiher (2016). The upper bound is a consequence of the Kruskal–Katona theorem .
See also
*
Erdős–Stone theorem
In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an ''H''-free graph for a non-complete graph ''H''. It is named after Paul Erdős and Arthur Stone, who pr ...
, a generalization of Turán's theorem from forbidden cliques to forbidden Turán graphs
References
{{DEFAULTSORT:Turans theorem
Extremal graph theory
Theorems in graph theory
Articles containing proofs