Editing Turán's theorem (section)

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