Proving $|E| \leq \frac{1}{2}(\sqrt{t-1}\;n^{3/2} + n$) in a graph with no copies of $K_{2,t}$

94 Views Asked by At

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!

1

There are 1 best solutions below

0
On BEST ANSWER

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.