Una desigualdad para gráficos

Question

En el medio de una prueba en una teoría de grafos libro en el que estoy mirando aparece la desigualdad $$\sum_i {d_i \choose r} \ge n { m /n \choose r},$$ y no estoy seguro de cómo lo justifican. Aquí $d_i$ es el grado de vértice $i$ y la suma es sobre todos los $n$ vértices. Hay $m$ bordes. Si es útil, creo que podemos asumir que $r$ es fijo e $n$ es grande y $m \approx n^{2 - \epsilon}$ algunos $\epsilon > 0$.

Mi único pensamiento es que puedo hacerlo si me vuelva a colocar todos los ${d_i \choose r}$$(d_i)^r / r!$, pero esto parece un poco descuidado.

También, para mis propósitos, me siento feliz, incluso con una sencilla prueba de que

$$\sum_i {d_i \choose r} \ge C \, n { m /n \choose r}$$ tiene para algunas constantes $C>0$.

Motivación: una forma aparentemente sencilla de contar el argumento da un límite inferior en el Frigyes número de la completa bipartito gráfico de $K_{r,s}$.

Fuente: Erdős en los Gráficos : Su Legado de Problemas sin resolver. En la edición que tengo, este aparece en la página.36.

---

La parte pertinente del texto del libro:

3.3. Frigyes Números para Grafos Bipartitos

Problema

¿Cuál es el entero más grande $m$ tal que no hay un gráfico de $G$ $n$ vértices y $m$ los bordes, que no contenga $K_{r,r}$ como un gráfico? En otras palabras, determinar el $t(n, K_{r,r})$.

.... para $2\le r \le s$ $$t(n,K_{r,s}) < cs^{1/r}n^{2-1/r}+O(n) \qquad (3.2)$$

La prueba de (3.2) es el siguiente recuento de argumento:

Supongamos que un gráfico de $G$ $m$ bordes y tiene el grado de secuencia $d_1,\ldots,d_n$. El número de copias de las estrellas $S_r$ $G$ es exactamente $$\sum_i \binom{d_i}r.$$ Por lo tanto, existe al menos una copia de $K_{r,t}$ $G$ si $$\frac{\sum_i \binom{d_i}r}{\binom nr} \ge \frac{n\binom{m/n}r}{\binom nr}>s$$ que tiene si $m\ge cs^{1/r}n^{2-1/r}$ para algunos apropiado constante $c$ (que depende de la $r$, pero es independiente de la $n$). Esto demuestra (3.2)

Answer 1

Fijar un número entero $r \geq 1$. A continuación, la función de $f: \mathbb R^{\geq 0} \to \mathbb R^{\geq 0}$ dada por $$ f(x) := \binom{\max \{ x, r-1 \}}{r} $$ es tanto monótona creciente y convexa.* De manera que al aplicar la desigualdad de Jensen a $f$ $n$ números de $d_1, d_2, \ldots, d_n$, obtenemos $$ \sum_{i=1}^n f(d_i) \geq n \ f\left(\frac{1}{n} \sum_{i=1}^n d_i \right). \etiqueta{1} $$

El reclamo en la pregunta de la siguiente manera mediante la simplificación de los laterales izquierdo y derecho:

• Observe que para cualquier entero$d$,$f(d) = \binom{d}{r}$. (Si $d < r$, $f(d)$ $\binom{d}{r}$ son cero.) De modo que el lado izquierdo se simplifica a $\sum \limits_{i=1}^n \binom{d_i}{r}$.

• Por otro lado, $\sum\limits_{i=1}^n d_i = 2m$ para cualquier gráfico. Por lo tanto, suponiendo que $2m/n \geq r-1$ (lo que parece razonable dada la amplia gama de parámetros, véase más abajo), el lado derecho de la $(1)$ simplifica a $n \cdot \binom{2m/n}{r}$. (A su vez, esto es, al menos, $n \cdot \binom{m/n}{r}$ que se afirma en la pregunta.)

EDIT: (Más de contexto ha sido añadido a la pregunta.) En el contexto del problema, tenemos $m \geq c s^{1/r} n^{2 - 1/r}$. Si $r > 1$, $m \geq c s^{1/r} n^{3/2} \geq \Omega(n^{3/2})$ (donde tratamos $r$ $s$ a ser fijos constantes, y deje $n \to \infty$). Por lo tanto, para suficientemente grande $n$,$m \geq n (r-1)$, y por lo tanto nuestra prueba tiene.

---

*Monotonía y la convexidad de $f$. Escribimos $f(x)$ como la composición de la $f(x) = h(g(x))$, donde $$ \begin{eqnarray*} g(x) &:=& \max \{ x - r + 1, 0 \} & \quad (x \geq 0); \\ h(y) &:=& \frac{1}{r!} y (y+1) (y+2) \cdots (y+r-1) & \quad (y \geq 0). \end{eqnarray*} $$

Observe que tanto $g(x)$ $h(y)$ son monótonamente creciente y convexa para todos en todas partes en $[0, \infty)$. (Es posible que ayude a darse cuenta de que $h$ es un polinomio con no negativo de los coeficientes; así que todos sus derivados son no negativos en todas partes en $[0, \infty)$.) Bajo estas condiciones, se deduce que el $f(x) = h(g(x))$ también es monótonamente creciente y convexa para todos los $x \geq 0$. (Ver la página de wikipedia para las correspondientes propiedades de las funciones convexas.)

EDIT: Corregido un error tipográfico. Necesitamos $2m/n \geq r-1$, en lugar de $2m \geq r-1$.