Show that the limit of the density of the Turán graph T(r,n) is 1-1/r+O(1).

Question

Some notes I have claim that as n tends to infinity the density of the Turán graph T(r,n) tends to 1-1/r+O(1). How can this be shown?

Answer 1

The easiest way to see this is to first assume that $r\mid n$, so $T(r,n)$ is the complete multipartite graph with $r$ parts, each of size $n/r$. Therefore, since $r$ is fixed, as $n\to\infty$, we have $$ |E(T(r,n))|={n\choose 2}-r{n/r\choose 2}={n^2\over 2}-r{(n/r)^2\over 2}+O(n)={n^2\over 2}\biggl(1-{1\over r}+O(1/n)\biggr) $$ Thus, the density is $$ {|E(T(r,n))|\over {n\choose 2}}=1-{1\over r}+O(1/n)=1-{1\over r}+o(1). $$ In the case that $r\nmid n$, $T(r,n)$ has $s$ parts of size $\lfloor n/r\rfloor+1$ and $r-s$ parts of size $\lfloor n/r\rfloor$. Writing ${\lfloor n/r\rfloor +1\choose 2}={\lfloor n/r\rfloor +1\over \lfloor n/r\rfloor -1}{\lfloor n/r\rfloor\choose 2}$, we see that as $n\to\infty$, since $r$ (and hence $s$) are fixed, we arrive at the same asymptotics.