Turán graph

{{infobox graph

| name = Turán graph

| image = 180px

| image_caption = The Turán graph T(13,4)

| namesake = Pál Turán

| vertices = $n$

| edges = ~ $\left(1- \frac{1}{r}\right)\frac{n^2}{2}$

| radius = $\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.$

| diameter = $\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.$

| girth = $\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.$

| chromatic_number = $r$

| chromatic_index =

| notation = $T(n,r)$

}}

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 different subsets. Where $q$ and $s$ are the quotient and remainder of dividing $n$ by $r$ (so $n = qr + s$ ), the graph is of the form $K_{q+1, q+1, \ldots, q, q}$ , and the number of edges is

: $\left(1 - \frac{1}{r}\right)\frac{n^2 - s^2}{2} + {s \choose 2}$ .

For $r\le7$ , this edge count can be more succinctly stated as $\left\lfloor\left(1-\frac1r\right)\frac{n^2}2\right\rfloor$ . 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. {{harvtxt|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 $\frac{r\,{-}\,1}{3r}(2\alpha -1)n^2$ edges, if α is sufficiently close to 1.{{sfnp|Keevash|Sudakov|2003}} 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.

Special cases

File:Complex tripartite graph octahedron.svg, a 3-cross polytope whose edges and vertices form K_2,2,2, a Turán graph T(6,3). Unconnected vertices are given the same color in this face-centered projection.]]

Several choices of the parameter r in a Turán graph lead to notable graphs that have been independently studied.

The Turán graph T(2n,n) can be formed by removing a perfect matching from a complete graph K_2n. As {{harvtxt|Roberts|1969}} showed, this graph has boxicity exactly n; it is sometimes known as the Roberts graph.{{sfnp|Roberts|1969}} This graph is also the 1-skeleton of an n-dimensional cross-polytope; for instance, the graph T(6,3) = K_2,2,2 is the octahedral graph, the graph of the regular octahedron. If n couples go to a party, and each person shakes hands with every person except his or her partner, then this graph describes the set of handshakes that take place; for this reason, it is also called the cocktail party graph.

The Turán graph T(n,2) is a complete bipartite graph and, when n is even, a Moore graph. When r is a divisor of n, the Turán graph is symmetric and strongly regular, although some authors consider Turán graphs to be a trivial case of strong regularity and therefore exclude them from the definition of a strongly regular graph.

The class of Turán graphs can have exponentially many maximal cliques, meaning this class does not have few cliques. For example, the Turán graph $T(n,\lceil n/3\rceil)$ has 3^a2^b maximal cliques, where

3a + 2b = n and b ≤ 2; each maximal clique is formed by choosing one vertex from each partition subset. This is the largest number of maximal cliques possible among all n-vertex graphs regardless of the number of edges in the graph; these graphs are sometimes called Moon–Moser graphs.{{sfnp|Moon|Moser|1965}}

Other properties

Every Turán graph is a cograph; that is, it can be formed from individual vertices by a sequence of disjoint union and complement operations. Specifically, such a sequence can begin by forming each of the independent sets of the Turán graph as a disjoint union of isolated vertices. Then, the overall graph is the complement of the disjoint union of the complements of these independent sets.

{{harvtxt|Chao|Novacky|1982}} show that the Turán graphs are chromatically unique: no other graphs have the same chromatic polynomials. Nikiforov (2005) uses Turán graphs to supply a lower bound for the sum of the kth eigenvalues of a graph and its complement.{{sfnp|Chao|Novacky|1982}}

{{harvtxt|Falls|Powell|Snoeyink|2003}} develop an efficient algorithm for finding clusters of orthologous groups of genes in genome data, by representing the data as a graph and searching for large Turán subgraphs.{{sfnp|Falls|Powell|Snoeyink|2003}}

Turán graphs also have some interesting properties related to geometric graph theory. {{harvtxt|Pór|Wood|2005}} give a lower bound of Ω((rn)^3/4) on the volume of any three-dimensional grid embedding of the Turán graph.{{sfnp|Pór|Wood|2005}} {{harvtxt|Witsenhausen|1974}} conjectures that the maximum sum of squared distances, among n points with unit diameter in R^d, is attained for a configuration formed by embedding a Turán graph onto the vertices of a regular simplex.{{sfnp|Witsenhausen|1974}}

An n-vertex graph G is a subgraph of a Turán graph T(n,r) if and only if G admits an equitable coloring with r colors. The partition of the Turán graph into independent sets corresponds to the partition of G into color classes. In particular, the Turán graph is the unique maximal n-vertex graph with an r-color equitable coloring.

Notes

References

{{cite journal

| journal = Discrete Mathematics

| volume = 41

| pages = 139–143

| year = 1982

| doi = 10.1016/0012-365X(82)90200-X

| issue = 2| doi-access = free

}}

{{cite web

| title = Computing high-stringency COGs using Turán type graphs

| year = 2003

}}

{{cite journal

| title = Local density in graphs with forbidden subgraphs

| year = 2003

| volume = 12

| pages = 139–153

| doi = 10.1017/S0963548302005539

| issue = 2|s2cid=17854032 |url=http://www.math.princeton.edu/~bsudakov/localdensity.pdf}}

{{Cite journal

| title = On cliques in graphs

| journal = Israel Journal of Mathematics

| volume = 3

| pages = 23–28

| year = 1965

| doi = 10.1007/BF02760024 | doi-access=

| s2cid = 9855414 }}

{{cite journal

| last = Nikiforov |first= Vladimir

| title = Eigenvalue problems of Nordhaus-Gaddum type

| year = 2007

| journal = Discrete Mathematics

| volume = 307

| issue = 6

| pages=774–780

| doi=10.1016/j.disc.2006.07.035 | doi-access=free

| arxiv = math.CO/0506260}}

{{cite conference

| title = No-three-in-line-in-3D

| publisher = Lecture Notes in Computer Science no. 3383, Springer-Verlag

| year = 2005

| pages = 395–402

| doi = 10.1007/b105810| hdl = 11693/27422

| hdl-access = free

}}

{{Cite journal

| last = Roberts | first = F. S. | author-link = Fred S. Roberts

| editor-last = Tutte

| editor-first = W.T.

| title = On the boxicity and cubicity of a graph

| journal = Recent Progress in Combinatorics

| year = 1969 | pages = 301–310

}}

{{cite journal

| last = Turán | first= P. | author-link = Pál Turán

| title = Egy gráfelméleti szélsőértékfeladatról (On an extremal problem in graph theory)

| journal = Matematikai és Fizikai Lapok

| volume = 48

| year = 1941

| pages = 436–452

}}

{{cite journal

| last = Witsenhausen|first= H. S.

| title = On the maximum of the sum of squared distances under a diameter constraint

| year = 1974

| journal = American Mathematical Monthly

| pages = 1100–1101

| volume = 81

| doi = 10.2307/2319046

| issue = 10

| jstor = 2319046}}

External links

{{mathworld | urlname = CocktailPartyGraph | title = Cocktail Party Graph}}
{{mathworld | urlname = OctahedralGraph | title = Octahedral Graph}}
{{mathworld | urlname = TuranGraph | title = Turán Graph}}

Category:Parametric families of graphs

Category:Extremal graph theory