# An inequality for graphs

In the middle of a proof in a graph theory book I am looking at appears the inequality $$\sum_i {d_i \choose r} \ge n { m /n \choose r},$$ and I'm not sure how to justify it. Here $d_i$ is the degree of vertex $i$ and the sum is over all $n$ vertices. There are $m$ edges. If it is helpful I think we can assume that $r$ is fixed and $n$ is large and $m \approx n^{2 - \epsilon}$ for some $\epsilon > 0$.

My only thought is that I can do it if I replace every ${d_i \choose r}$ by $(d_i)^r / r!$, but this seems a little sloppy.

Also, for my purposes, I am happy with even a quick-and-dirty proof that

$$\sum_i {d_i \choose r} \ge C \, n { m /n \choose r}$$ holds for some constant $C>0$.

Motivation: an apparently simple counting argument gives a lower bound on the Turán number of the complete bipartite graph $K_{r,s}$.

Source: Erdős on Graphs : His Legacy of Unsolved Problems. In the edition I have, this appears on p.36.

Relevant part of the text of the book:

3.3. Turán Numbers for Bipartite Graphs

Problem

What is the largest integer $m$ such that there is a graph $G$ on $n$ vertices and $m$ edges which does not contain $K_{r,r}$ as a graph? In other words, determine $t(n, K_{r,r})$.

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

The proof of (3.2) is by the following counting argument:

Suppose a graph $G$ has $m$ edges and has degree sequence $d_1,\ldots,d_n$. The number of copies of stars $S_r$ in $G$ is exactly $$\sum_i \binom{d_i}r.$$ Therefore, there is at least one copy of $K_{r,t}$ contained in $G$ if $$\frac{\sum_i \binom{d_i}r}{\binom nr} \ge \frac{n\binom{m/n}r}{\binom nr}>s$$ which holds if $m\ge cs^{1/r}n^{2-1/r}$ for some appropriate constant $c$ (which depends of $r$ but is independent on $n$). This proves (3.2)

-
I added the part of the text from the book which seemed relevant to me. (This might be useful for the answerers.) I hope this qualifies as a fair use. meta.math.stackexchange.com/questions/2600/… –  Martin Sleziak Nov 1 '11 at 7:44
@Martin Thanks for typing up the relevant portion of the problem from the text. –  Srivatsan Nov 1 '11 at 8:10

Fix an integer $r \geq 1$. Then the function $f: \mathbb R^{\geq 0} \to \mathbb R^{\geq 0}$ given by $$f(x) := \binom{\max \{ x, r-1 \}}{r}$$ is both monotonically increasing and convex.* So applying Jensen's inequality to $f$ for the $n$ numbers $d_1, d_2, \ldots, d_n$, we get $$\sum_{i=1}^n f(d_i) \geq n \ f\left(\frac{1}{n} \sum_{i=1}^n d_i \right). \tag{1}$$

The claim in the question follows by simplifying the left and right hand sides:

• Notice that for any integer $d$, we have $f(d) = \binom{d}{r}$. (If $d < r$, then both $f(d)$ and $\binom{d}{r}$ are zero.) So the left hand side simplifies to $\sum \limits_{i=1}^n \binom{d_i}{r}$.

• On the other hand, $\sum\limits_{i=1}^n d_i = 2m$ for any graph. Therefore, assuming that $2m/n \geq r-1$ (which seems reasonable given the range of parameters, see below), the right hand side of $(1)$ simplifies to $n \cdot \binom{2m/n}{r}$. (In turn, this is at least $n \cdot \binom{m/n}{r}$ that is claimed in the question.)

EDIT: (More context has been added to the question.) In the context of the problem, we have $m \geq c s^{1/r} n^{2 - 1/r}$. If $r > 1$, then $m \geq c s^{1/r} n^{3/2} \geq \Omega(n^{3/2})$ (where we treat $r$ and $s$ to be fixed constants, and let $n \to \infty$). Hence, for sufficiently large $n$, we have $m \geq n (r-1)$, and hence our proof holds.

*Monotonicity and convexity of $f$. We write $f(x)$ as the composition $f(x) = h(g(x))$, where $$\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*}$$

Notice that both $g(x)$ and $h(y)$ are monotonically increasing and convex for all everywhere in $[0, \infty)$. (It might help to observe that $h$ is a polynomial with nonnegative coefficients; so all its derivatives are nonnegative everywhere in $[0, \infty)$.) Under these conditions, it follows that $f(x) = h(g(x))$ is also monotonically increasing and convex for all $x \geq 0$. (See the wikipedia page for the relevant properties of convex functions.)

EDIT: Corrected a typo. We need $2m/n \geq r-1$, rather than $2m \geq r-1$.

-
It's not obvious to me that $h$ is convex for $y \ge r-1$. Is this straightforward? –  Qiaochu Yuan Nov 1 '11 at 4:46
@Qiaochu It's actually easier than I thought. Instead of $\binom{y}{r}$ ($y \geq r -1$), imagine the shifted version of the function $\binom{y+r-1}{r}$ (for $y \geq 0$), which has the shape $y(y+1)(y+2) \cdots (y+r-1)$ (ignoring the $r!$ factor in the front). This is clearly convex for $y \geq 0$ since all its derivatives are nonnegative. –  Srivatsan Nov 1 '11 at 5:03
@Qiaochu I rewrote the composition slightly to make the proof more direct. Hopefully this is clearer. (Thanks for the question, by the way.) –  Srivatsan Nov 1 '11 at 5:28
Don't you need $2m/n \geq r-1$ instead of $2m \geq r-1$ to simplify the RHS of Jensen's inequality? (Of course, I could have missed something.) –  Martin Sleziak Nov 1 '11 at 7:26
@Martin You are absolutely right. That was my mistake. EDIT: Corrected now. Thanks! –  Srivatsan Nov 1 '11 at 7:29