Editing Turán graph

{{Short description|Balanced complete multipartite graph}}
{{infobox graph
 | name = Turán graph
 | image = [[Image:Turan 13-4.svg|180px]]
 | image_caption = The Turán graph T(13,4)
 | namesake = [[Pál Turán]]
 | vertices = <math>n</math>
 | edges = ~<math>\left(1- \frac{1}{r}\right)\frac{n^2}{2}</math>
 | radius = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.</math>
 | diameter = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.</math>
 | girth = <math>\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.</math>
 | chromatic_number = <math>r</math>
 | chromatic_index =
 | notation = <math>T(n,r)</math>
}}
The '''Turán graph''', denoted by <math>T(n,r)</math>, is a [[complete multipartite graph]]; it is formed by [[partition of a set|partitioning a set]] of <math>n</math> vertices into <math>r</math> 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 <math>q</math> and <math>s</math> are the quotient and remainder of dividing <math>n</math> by <math>r</math> (so <math>n = qr + s</math>), the graph is of the form <math>K_{q+1, q+1, \ldots, q, q}</math>, and the number of edges is
:<math> \left(1 - \frac{1}{r}\right)\frac{n^2 - s^2}{2} + {s \choose 2}</math>.

For <math>r\le7</math>, this edge count can be more succinctly stated as <math>\left\lfloor\left(1-\frac1r\right)\frac{n^2}2\right\rfloor</math>. The graph has <math>s</math> subsets of size <math>q+ 1 </math>, and <math>r - s</math> subsets of size <math>q</math>; each vertex has degree <math>n-q-1</math> or <math>n-q</math>. It is a [[regular graph]] if <math>n</math> is divisible by <math>r</math> (i.e. when <math>s=0</math>).

==Turán's theorem==
{{Main|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''&nbsp;+&nbsp;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 (graph theory)|clique]] of size&nbsp;''r''&nbsp;+&nbsp;1. According to Turán's theorem, the Turán graph has the maximum possible number of edges among all (''r''&nbsp;+&nbsp;1)-clique-free graphs with ''n''&nbsp;vertices. {{harvtxt|Keevash|Sudakov|2003}} show that the Turán graph is also the only (''r''&nbsp;+&nbsp;1)-clique-free graph of order ''n'' in which every subset of &alpha;''n'' vertices spans at least <math>\frac{r\,{-}\,1}{3r}(2\alpha -1)n^2</math> 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|thumb|150px|The [[octahedron]], a 3-[[cross polytope]] whose edges and vertices form ''K''<sub>2,2,2</sub>, 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''(2''n'',''n'') can be formed by removing a [[perfect matching]] from a [[complete graph]] ''K''<sub>2''n''</sub>. 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 (topology)|skeleton]] of an ''n''-dimensional [[cross-polytope]]; for instance, the graph ''T''(6,3)&nbsp;=&nbsp;''K''<sub>2,2,2</sub> 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 graph|symmetric]] and [[Strongly regular graph|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 [[Graphs with few cliques|few cliques]]. For example, the Turán graph <math>T(n,\lceil n/3\rceil)</math> has 3<sup>''a''</sup>2<sup>''b''</sup> [[maximal clique]]s, where
3''a''&nbsp;+&nbsp;2''b''&nbsp;=&nbsp;''n'' and ''b''&nbsp;≤&nbsp;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 (graph theory)|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 polynomial]]s. Nikiforov (2005) uses Turán graphs to supply a lower bound for the sum of the ''k''th [[eigenvalue]]s 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'')<sup>3/4</sup>) on the volume of any three-dimensional [[Graph drawing|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'''<sup>''d''</sup>, 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 [[Glossary of graph theory#Subgraphs|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 ==
{{reflist}}

== References ==
{{refbegin|30em}}
* {{cite journal
  |last1=Chao|first1= C. Y. |last2=Novacky|first2= G. A. | title = On maximally saturated graphs
  | journal = [[Discrete Mathematics (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
  |last1=Falls|first1= Craig |last2=Powell|first2= Bradford |last3=Snoeyink|first3= Jack | url = http://www.cs.unc.edu/~snoeyink/comp145/cogs.pdf
 | year = 2003
  }}
* {{cite journal
  | title = Local density in graphs with forbidden subgraphs
  |last1=Keevash|first1= Peter |last2=Sudakov|first2= Benny | journal = [[Combinatorics, Probability and Computing]]
  | 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
  | last1 = Moon | first1 = J. W. | last2 = Moser | first2 = L. | author-link2 = Leo Moser
  | 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 (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
  |last1=Pór|first1= Attila |last2=Wood|first2= David R. |author2-link=David Wood (mathematician)| book-title = [[International Symposium on Graph Drawing|Proc. Int. Symp. Graph Drawing (GD 2004)]]
  | 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}}
{{refend}}

== External links ==
{{commons category|Turán graphs}}
* {{mathworld | urlname = CocktailPartyGraph | title = Cocktail Party Graph}}
* {{mathworld | urlname = OctahedralGraph | title = Octahedral Graph}}
* {{mathworld | urlname = TuranGraph | title = Turán Graph}}

{{DEFAULTSORT:Turan graph}}
[[Category:Parametric families of graphs]]
[[Category:Extremal graph theory]]