7
$\begingroup$

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)

  • 0
    @Martin Thanks for typing up the relevant portion of the problem from the text.2011-11-01

1 Answers 1

5

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$.

  • 0
    @Martin You can look at it that way. I was looking at it as using the monotonicity of $\binom{\cdot}{r}$ in the range $[r-1, \infty)$. (So all I needed was the statement that $\binom{2m/n}{r} \geq \binom{m/n}{r-1}$, which doesn't need the monotonicity of $f$, technically speaking.) But they are essentially the same thing...2011-11-01