recently I'm facing problems while trying to prove the following theorem:
Theorem: Let Ka,b denote the complete bipartite graph with a and b vertices in its color-classes. Then: $$ex(n,K_{a,b}) \leq \frac{1}{2} \sqrt[a]{b-1} \cdot n^{2-(1/a)} + \frac{a-1}{2}n.$$
I have only the sketch of the proof, which is the following one:
Sketch of the proof: The number of a-stars $K_{a,1}$ in a graph $G_{n}$ is $\sum \binom{d_{i}}{a}$, where d1, . . . , dn are the degrees in $G_{n}$. If $G_{n}$ contains no $K_{a,b}$ then at most b −1 of these a-stars can share the same set of endpoints. We obtain $$\sum \binom{d_{i}}{a} = \text{the number of a−stars} ≤ (b − 1)\binom{n}{a}$$
Extending $\binom{n}{a}$ to all $x>0$ by
$\binom{x}{a} = x(x-1)...(x-a+1)$ for $x>= a-1$ and $0$ for $x < a-1$
we have a convex function. Then Jensen’s Inequality implies that, the left hand side in exponated inequality above is at least $\binom{e(G)/n}{a}$, and the result follows by an easy calculation. End of sketch.
I understand the beginning, the proof of convexity is also obvious for me. But I can't follow how the Jensen's Inequality was used here, and how further calculations gives us final result.
Maybe somebody will be interested in the topic? Thank you in advance for the discussion.
There are a couple errors in your proof sketch which may be preventing you from successfully filling out the details. Here are some points to consider.
We define $\binom{x}{a}$ for real $x$ and integer $a$ to be $x(x-1)\cdots (x-a+1)/a!$ (and only for $x \geq a-1$ as you've stated).
Jensen's inequality states the following: let $f$ be a convex function and let $x_1,\dots, x_n$ be real. For any arithmetic (weighted) average $\bar{x} = \sum \lambda_i x_i$, we have $f(\bar{x}) \leq \sum \lambda_i f(x_i)$. For the unweighted arithmetic average, this means $nf(\bar{x}) \leq f(x_1) + \cdots f(x_n)$.
Since $\binom{x}{a}$ is convex in $x$, we may lower bound $\sum \binom{d_i}{a}$ by $n\binom{\bar{d}}{a}$, where $\bar{d} = e(G)/n$ is the average degree on one side of the bipartite graph $G$.
To follow the further calculation, we need to simplify the expressions involving the binomial coefficients. We first multiply both sides by $a!$. We bound $\binom{x}{a}$ below by $(x-a+1)^a$ and above by $x^a$.
The final error is that I believe the result of the theorem should be multiplied by a factor of $2$.