Turán's theorem

Turán's theorem

In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.

An n-vertex graph that does not contain any (r + 1)-vertex clique may be formed by partitioning the set of vertices into r parts of equal or nearly-equal size, and connecting two vertices by an edge whenever they belong to two different parts. We call the resulting graph the Turán graph T(n,r). Turán's theorem states that the Turán graph has the largest number of edges among all Kr+1-free n-vertex graphs.

Turán graphs were first described and studied by Hungarian mathematician Paul Turán in 1941, though a special case of the theorem was stated earlier by Mantel in 1907.

Contents

Formal statement

Formally, Turán's theorem may be stated as follows.

Let G be any subgraph of Kn such that G is Kr+1 -free. Then the number of edges in G is at most

\frac{r-1}{r}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{r} \right) \cdot\frac{n^2}{2}.

An equivalent formulation is the following:

Among the n-vertex simple graphs with no (r + 1)-cliques, T(n,r) has the maximum number of edges.

Proof

Let G be an n-vertex simple graph with no (r + 1)-clique and with the maximum number of edges.

Overview: The proof consists of two claims about G, which we outline, before proving.

The first claim is that G must be a complete r-partite graph (although it's stated more technically below). In other words, we can partition the vertex set into r subsets S_1, S_2,\ldots,S_r such that if two vertices are in different sets, Si and Sj, then they have an edge between them, but if they are in the same set, then they have no edge between them. The second claim is that the sizes of these sets Si differ from each other by at most 1. For example, if we want the graph on 23 vertices with the most edges that does not contain a triangle, then we partition the vertices into sets S1 and S2, with | S1 | = 12 and | S2 | = 11. We add all the edges between the two sets, so the graph will have 11*12 = 132 edges. This matches with the theorem, which says that G will have at most \frac{1}{2}\frac{23^2}{2} = \frac{23^2}4 = 132.25 edges.

Claim 1: Graph G does not contain any three vertices u,v,w such that G contains edge uv, but contains neither edge uw nor vw.

(This claim is equivalent to the relation x~y iff x not connected to y being an equivalence relation. ~ is always reflexive and symmetric, but only in special cases is it transitive. ~ is not transitive precisely when we have u, v and w with u ~ w and w ~ v without u ~ v.)

Assume the claim is false. Construct a new n-vertex simple graph G' that contains no (r + 1)-clique but has more edges than G, as follows:

Case 1: d(w) < d(u) or d(w) < d(v).

Assume that d(w) < d(u). Delete vertex w and create a copy of vertex u (with all of the same neighbors as u); call it u'. Any clique in the new graph contains at most one vertex among {u,u'}. So this new graph does not contain any (r + 1)-clique. However, it contains more edges: | E(G') | = | E(G) | − d(w) + d(u) > | E(G) | .

Case 2: d(w)\geq d(u) and d(w)\geq d(v)

Delete vertices u and v and create two new copies of vertex w. Again, the new graph does not contain any (r + 1)-clique. However it contains more edges: |E(G')| = |E(G)| -(d(u) + d(v) - 1) + 2d(w) \geq |E(G)| + 1.

This proves Claim 1.

The claim proves that one can partition the vertices of G into equivalence classes based on their nonneighbors; i.e. two vertices are in the same equivalence class if they are nonadjacent. This implies that G is a complete multipartite graph (where the parts are the equivalence classes).

Claim 2: The number of edges in a complete k-partite graph is maximized when the size of the parts differs by at most one.

If G is a complete k-partite graph with parts A and B and | A | > | B | + 1, then we can increase the number of edges in G by moving a vertex from part A to part B. By moving a vertex from part A to part B, the graph loses | B | edges, but gains | A | − 1 edges. Thus, it gains at least |A|-1-|B|\geq 1 edge. This proves Claim 2.

This proof shows that the Turan graph has the maximum number of edges. Additionally, the proof shows that the Turan graph is the only graph that has the maximum number of edges.

Mantel's theorem

As a special case of Turán's theorem, for r = 2, one obtains Mantel's theorem:

The maximum number of edges in an n-vertex triangle-free graph is \lfloor n^2/4 \rfloor.

In other words, one must delete nearly half of the edges in Kn to obtain a triangle-free graph.

A strengthened form of Mantel's theorem states that any graph with at least n2/4 edges must either be the complete bipartite graph Kn/2,n/2 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 (Bondy 1971).

Another strengthening of Mantel's theorem states that the edges of any graph may be covered by at most \lfloor n^2/4 \rfloor cliques: that is, the intersection number is at most \lfloor n^2/4 \rfloor (Erdős, Goodman & Pósa 1966).

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Turán graph — The Turán graph T(13,4) Named after Pál Turán v · …   Wikipedia

  • Turán sieve — In number theory, the Turán sieve is a technique for estimating the size of sifted sets of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Pál Turán in 1934.DescriptionIn terms of sieve… …   Wikipedia

  • 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 proved it in… …   Wikipedia

  • Pál Turán — à l université de Leipzig en 1955 Naissance 18 août 1910 Budapest ( …   Wikipédia en Français

  • Pál Turán — Paul (Pál) Turán Born 18 August 1910 …   Wikipedia

  • Szemerédi's theorem — In number theory Szemerédi s theorem refers to the proof of the Erdős–Turán conjecture. In 1936 Erdős and Turan conjecturedcitation|authorlink1=Paul Erdős|first1=Paul|last1=Erdős|authorlink2=Paul Turán|first2=Paul|last2=Turán|title=On some… …   Wikipedia

  • Satz von Turán — Der Satz von Turán (nach Pál Turán) ist eine Aussage aus dem mathematischen Teilgebiet der Graphentheorie. Er macht eine Aussage über die maximale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl haben kann, ohne einen vollständigen… …   Deutsch Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Method of conditional probabilities — In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic they work by showing that a random object, chosen from some… …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”