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

Question

Un gráfico de Turan $T_r(n)$ se define como la totalidad de $r$ -partita de orden $n$ tal que el número de vértices en cada uno de los $r$ las clases es $\lfloor \frac{n}{r}\rfloor$ o $\lceil \frac{n}{r} \rceil$ . Para las instalaciones fijas $n$ y $r$ , $T_r(n)$ es única hasta el isomorfismo. El tamaño de $T_r(n)$ puede contarse 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: suponer $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 menor que $1 - \frac{1}{r}$ como se ve al tomar $n=31$ y $r=5$ .

Answer 1

El tamaño $S$ del gráfico de Turán es $\frac 12\left(n^2-\frac {(n^2-s^2)}{r}-s\right)$ , ver mi respuesta . A continuación $$S- \left(1 - \frac{1}{r}\right) \binom{n}{2}=\frac{(n-s)(r-1)+s(s-1)}{2r}\ge 0.$$

Answer 2

Dejemos que $e$ sea el número de aristas y $a$ el grado medio de un vértice. Queremos demostrar que $$e\ge\left(1-\frac1r\right)\binom n2.$$ Desde $e=\frac{na}2$ y $\binom n2=\frac{n(n-1)}2$ , eso es lo mismo que mostrar $$\frac{na}2\ge\left(1-\frac1r\right)\frac{n(n-1)}2,$$ es decir, tenemos que demostrar que $$a\ge\left(1-\frac1r\right)(n-1).$$ Dado que el grado de cada vértice es $n-\lfloor\frac nr\rfloor$ o $n-\lceil\frac nr\rceil$ y como $\lceil\frac nr\rceil\le\frac{n+r-1}r=1+\frac{n-1}r$ tenemos $$a\ge n-\left\lceil\frac nr\right\rceil\ge n-\left(1+\frac{n-1}r\right)=\left(1-\frac1r\right)(n-1),$$ Q.E.D.