# Alternative way to calculate number of edges in Turán-graphs?

We define a Turán-graph $$T_n(r) = K_{\lceil\frac{n}{r}\rceil, \ldots,\lceil\frac{n}{r}\rceil, \lfloor\frac{n}{r}\rfloor, \ldots, \lfloor\frac{n}{r}\rfloor}$$

with $$n \bmod r$$ many subsets $$V_i$$ that contain $$\lceil\frac{n}{r}\rceil$$ many vertices and $$r- (n \bmod r)$$ many subsets with $$\lfloor\frac{n}{r}\rfloor$$ vertices. Let $$n=pr+q$$. We calculate the number of edges in such a graph as follows $$t_n(r) = \left( 1 - \frac{1}{r}\right)\frac{n^2}{2} - \frac{q(r-q)}{2r}$$

## My thoughts:

We can think of Turán-graphs as $$r$$-partit graphs. So for some $$T_n(r) = K_{V_1, V_2, \ldots, V_r}$$ with $$e_{i} = \binom{i}{2}$$ representing the number of edges in some complete graph $$K_i$$.

Hence, we can calculate the number of edges as follows: \begin{align*} t_n'(r) &= e_{n} - e_{V_1} - e_{V_2} - \ldots - e_{V_r} \\ &= \binom{n}{2} - \binom{V_1}{2} - \binom{V_2}{2} - \ldots -\binom{V_r}{2}\end{align*}

## Question:

This seems way more simple to me than the formula given above. If $$t_n'(r)$$ works correct (couldn't prove it wrong nor right), why bother using $$t_n(r)$$?

Your formula is fine. It is essentially what Wikipedia's article is using in the introduction at the moment, for example. I think it's not as simple as you believe: to have a complete formula we should include the sizes of the parts, which gives us $$t'(n,r) = \binom n2 - (n \bmod r) \binom{\lceil n/r\rceil}{2} - (r - (n \bmod r))\binom{\lfloor n/r \rfloor}{2}.$$ It is still a perfectly good formula.
The advantage of $$t(n,r)$$ is that it tells us the "nice approximation" $$(1 - \frac1r) \frac{n^2}{2}$$ first, and then it gives the error in that approximation.
Watch out for the incorrect formula $$\left\lfloor \frac{(r-1)n^2}{2r}\right\rfloor = \left\lfloor \Big(1 - \frac1r\Big)\frac{n^2}{2}\right\rfloor$$ found on Wolfram MathWorld and other sources that cite it. It agrees with the correct formula in many cases, in particular for all small values of $$r$$. This formula is first wrong when $$n=12$$ and $$r=8$$: it gives $$63$$, while the number of edges in $$K_{2,2,2,2,1,1,1,1}$$ is only $$62$$. In general, it may be too high by as much as $$\frac r8$$: the upper bound on the $$\frac{q(r-q)}{2r}$$ error term in the first formula, where $$q = n \bmod r$$.
• But looking at what I've written, I'm suddenly confused how the error can be at most $1$ and simultaneously as large as $\frac{q(r-q)}{2r}$, so I'll have to look into that... Apr 5 '21 at 12:41