Skip to main content
4 of 6
added 61 characters in body
Mike
  • 1k
  • 6
  • 14

@Megan, I think you meant in your original statement

Let $r$ and $s$ be fixed numbers. Then KST theorem says that for some constant $c = c(r,s)$, a graph with at least $c(r,s)n^{2-\frac{1}{r}}$ edges contains a copy of $K_{r,s}$.

If a graph w $c(r,s)n^{2-\frac{1}{r}}$ edges contains a copy of $K_{r,s}$ then for any positive $c'$, a graph in $G$ with $c(r,s)n^{2-\frac{1}{r}} + c'n$ edges definitely contains $c'n$ copies of $K_{r,s}$ given KSK stated above. Indeed, you can find a copy of $K_{r,s}$ in $G$ and remove an edge from the copy, and then find a copy of $K_{r,s}$ in the remaining graph ($G$ minus the edge removed), and so on and so forth, $c'n$ times, to get $c'n$ distinct copies of $K_{r,s}$.

If $c'$ is less than 1, then $c'n$ is small relative to $c(r,s)n^{2-\frac{1}{r}}$ so the following can be concluded from KSK theorem as written above plus the previous paragraph:

Let $r$ and $s$ be fixed numbers. Then for some constant $\tilde{c} = \tilde{c}(r,s)$, a graph with at least $\tilde{c}(r,s)n^{2-\frac{1}{r}}$ edges contains at least $n$ copies of $K_{r,s}$.

For larger values of $c'n$ the above argument probably can be tightened further.

Mike
  • 1k
  • 6
  • 14