Экстремальные задачи (теорема Турана)

Если граф не содержит треугольников, то $e \leq n^{2}/4$.

Если $e = [n^{2}/4] + 1$, то в графе есть по крайней мере $[n/2]$ треугольников.

Если $n = km$ и граф не содержит $(k+1)$-клики, то $2e \leq k(k-1) \times m^{2}$. (Переходя к дополнительному графу, получаем, что если $n = km$ и граф не содержит $(k+1)$-антиклики, то $2e \geq km(m-1)$.)

Если граф не содержит $(k+1)$-антиклики, то $2e \geq km(m-1) + 2mr$, где $m := [n/k]$ и $r := k\{ n/k\}$.

Если граф не содержит несамопересекающегося цикла длины 4, то $e < n^{3/2}$.

Если граф не содержит подграфа $K_{3,2}$, то $e < 2n^{3/2}$.

Если граф не содержит подграфа $K_{3,3}$, то $e < 2n^{5/3}$.

Для любых целых $s, t$, $2 \leq s \leq t$, если граф не содержит подграфа $K_{s,t}$, то $e < t n^{2-1/s}$.

$E_{n}(2) > n[\log_{2} n]/4$;

$E_{n}(2) \leq 2n^{3/2}$;

$E_{n}(3) \leq 2n^{5/3}$;

$\dfrac {(n-1)^{2}}{4} \leq E_{n}(4) \leq \dfrac {2(n+4)^{2}}{5}$.

Пусть $V$ — $11^{q}$-элементное подмножество пространства $\mathbb {R}^{q}$ (определение пространства $\mathbb {R}^{q}$ см. в гл. 7), любое $10^{q}$-элементное подмножество которого содержит две точки $x,y$ на расстоянии 1: $\left|x-y\right|=1$. Докажите, что для достаточно большого $q$ количество единичных расстояний между точками множества $V$ больше чем $12^{q}/2$:

Докажите, что в условиях предыдущего пункта можно заменить число $12^{q}/2$ на $12{,}1^{q}$.