Demuestre que el tamaño del gráfico de Turan Tr(n)Tr(n)T_r(n) es al menos (1−1r)(n2)(1−1r)(n2)(1 - \frac{1}{r} ) \binom{n}{2}.

Un gráfico de Turan$T_r(n)$se define como el completo$r$-gráfico de partículas de orden$n$tal que el número de vértices en cada uno de los$r$las clases son$\lfloor \frac{n}{r}\rfloor$o$\lceil \frac{n}{r} \rceil$. para fijo$n$y$r$,$T_r(n)$es único hasta el isomorfismo. La talla de$T_r(n)$se puede contar simplemente como:$\binom{n}{2} - (n \bmod r) \binom{\lceil \frac{n}{r} \rceil}{2} - (r - (n\bmod r))\binom{\lfloor \frac{n}{r}\rfloor}{2}$.

Esto es lo que tengo: asumir$n = kr + s,\ 0 \leq s \leq r-1$. Tenga en cuenta que al menos una clase debe tener exactamente$\lfloor \frac{n}{r} \rfloor$vértices. Entonces,$\binom{n}{2} - (n \bmod r) \binom{\lceil \frac{n}{r} \rceil}{2} - (r - (n\bmod r))\binom{\lfloor \frac{n}{r}\rfloor}{2}$

$\geq$ $\binom{n}{2} -(r-1) \binom{\lceil \frac{n}{r} \rceil}{2} - \binom{\lfloor \frac{n}{r} \rfloor}{2}$

$=\binom{n}{2} - (r-1) \binom{k+1}{2} - \binom{k}{2}$

$= \frac{n(n-1)}{2} - \frac{(r-1)k(k+1)}{2} - \frac{k(k-1)}{2}$

$= \frac{n(n-1)}{2} - \frac{rk(k+1) - k(k+1)}{2} - \frac{k(k-1)}{2}$

$\geq \frac{n(n-1)}{2} - \frac{n(k+1) - k(k+1)}{2} - \frac{k(k-1)}{2}$

$= \frac{n(n-1)-n(k+1) + k(k+1) - k(k-1)}{2}$

$= \frac{n(n-1)-n(k+1) + 2k}{2}$

$= \binom{n}{2}(1 - \frac{k+1}{n-1} + \frac{2k}{n(n-1)})$.

Pero claramente,$(1 - \frac{k+1}{n-1} + \frac{2k}{n(n-1)})$puede ser más pequeño que$1 - \frac{1}{r}$, como se ve tomando$n=31$y$r=5$.