# non existence of $K_{r,r}$ in a given graph on any number of vertices

I need to prove that: for every r>1 there exists $c>0$, s.t for every $n$, there exists some $G$, a graph on $n$ vertices, with average degree $cn^{1-\frac{2}{r}}$ (or above), s.t $K_{r,r}\nsubseteq G$.

I am trying to use the probabilistic method here in a few ways: Looking at all the possible edges in a random (uniformly distributed) order and adding them to the graph, or trying to find the expectancy of the existence of $K_{r,r}$ given $2r$ vertices, but with no luck.

Any help? Am I even in the right direction? Thanks :)

-
Could you explain how you tried to calculate the expected number of $K_{r,r}$ in a random graph, without any luck? – Erick Wong Jun 10 '12 at 21:26

I don't have time to answer this properly, but I'll get you headed in the right direction. Perhaps some bounty hunter will fill in the details [or you can]. I would start by including edges independently with probability $p = cn^{-2/r}$ (this will roughly give your average degree condition). For a given $r$ vertices and another given $r$ vertices, there are $r^2$ edges to check to see if there is a $K_{r,r}$ (note that I specify the partition beforehand). The probability that there is a $K_{r,r}$ on this specific partition is $(cn^{-2/r})^{r^2} = c^{r^2} n^{-2r}$. Since there are at most $n^{2r}$ partitions to check, the probability that you have at least one $K_{r,r}$ is (by a union bound) at most $n^{2r} \cdot c^{r^2} n^{-2r} = c^{r^2}$. So $1-c^{r^2}$ proportion of the graphs have no $K_{r,r}$ . Now you just need to argue that the one of the graphs in this proportion meets your average degree condition.
Note that the expected value of the number of edges is $c\binom{n}{2}n^{-2/r}$, by linearity of expectation. Most of this binomial random variable is concentrated close to expected value [using concentration results; Chebyshev might be enough here, or some other result might work]. This should be able to finish it off, as it will give that for suitable $c$ most of the graphs have high average degree, and also most of the graphs have no $K_{r,r}$. If most have one property or the other, then there has to be one with both of those properties.
Ok, I think I'm close to it. But still a problem: $\begin{pmatrix}n\\ 2\end{pmatrix}p=\frac{n\left(n-1\right)}{2}cn^{-\frac{2}{r}}=\frac{n-1}{2}cn^{1-‌​\frac{2}{r}}$ and therefore the expected average degree is $\left(n-1\right)cn^{-\frac{2}{r}}=cn^{1-\frac{2}{r}}-cn^{-\frac{2}{r}}$ which is lower then what I need. then how can I ensure that most of the graphs will have high average degree? – IBS Jun 14 '12 at 12:38
$cn^{1-\frac{2}{r}} - cn^{-\frac{2}{r}} = cn^{1-\frac{2}{r}}(1-o(1))$, so this shouldn't pose a problem since you can make the value that you take for $c$ smaller. – John Engbers Jun 14 '12 at 13:21
Upper bound the variance of the number of edges (a binomial r.v.) by $n^2 p = cn^{2(1-1/r)}$. Then $\sigma \leq cn^{1-1/r}$ ($c$ changes, of course). Chebyshev says that the likelihood of being more than $2\sigma$ away (2 may be increased too) from the expected value (in number of edges) is at most 1/4. So with probability at least 3/4 you have at least $\binom{n}{2}p - 2\sigma$ edges. Put all of these things together to give that for a correctly chosen $c$, $\geq 3/4$ have the right average degree, and $\geq 3/4$ have no $K_{r,r}$. This should finish it - just write it up nicely. – John Engbers Jun 18 '12 at 14:53