Skip to main content
1 of 6
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) $c'n$ times.

If $c'$ is less than 1, then $c'n$ is small relative to $c(r,s)n^{2-\frac{1}{r}}$ so the KSK theorem can be written.

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

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

Mike
  • 1k
  • 6
  • 14