Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.