Show that if an $n$-vertex graph $G=(V,E)$ has no copy of $K_{2,t}$ then: $$|E| \leq \frac{1}{2}(\sqrt{t-1}\;n^{3/2} + n)$$

I know how to prove it for $n=2: \;$ Dentoe $|E|=m,$ $d(v)$ the degree of $v$ for every $v \in V$. Then: $$n \cdot\binom{\frac{2m}{n}}{2} \leq \sum_{v \in V} \binom{d(v)}{2}= \#K_{1,2} \leq \binom{n}{2}$$

The first inequality follows from the fact that the function $x \to \binom{x}{2}$ is convex and using jensen's inequality, and the last inequality is because the graph has no copies of $K_{2,t}$.

By using similar arguments, I got:

$$n \cdot\binom{\frac{2m}{n}}{t} \leq \sum_{v \in V} \binom{d(v)}{t}= \#K_{1,t} \leq \binom{n}{t}$$

But here I'm having some trouble getting to the final result. Is this the right way to go? any help would be appreciated!


It's a right way to go in the sense that it will give you a bound on $m$, but it will not give you the best bound. You've chosen the wrong generalization of $K_{2,2}$ to $K_{2,t}$. Instead of looking at $t$-element subsets of each neighborhood (which must cover each of $\binom nt$ $t$-element sets at most once) you should continue looking at $2$-element subsets of each neighborhood (which now cover each of $\binom n2$ $2$-element sets at most $t-1$ times).

Then, by using convexity in exactly the way you have been doing, we have $$ n \binom{2m/n}{2} \le \sum_{v \in V} \binom{d(v)}{2} \le (t-1) \binom n2. $$ Or, to avoid dealing with inconvenient factors, we can write a slightly weaker but simpler inequality: $$ n \cdot \frac{(2m/n - 1)^2}{2} \le (t-1) \cdot \frac{n^2}{2}. $$ Solving for $m$, you will get the bound you want.

There's nothing special about $2$, and in fact the same approach gives you the Kővári–Sós–Turán theorem: that an $n$-vertex graph with no copies of $K_{s,t}$ has at most $O(n^{2-1/s})$ edges. Just as in the case of $K_{2,t}$, there are two ways to look at $K_{s,t}$, and the other way gives a bound of $O(n^{2-1/t})$; we use whichever is better. However, for $K_{2,t}$, a result of Füredi gives a matching lower bound construction, which is not known to exist in general.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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