2
$\begingroup$

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)$?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$ Apr 5 '21 at 12:41
  • $\begingroup$ Thought that's because some errors are cancelling out each other since we round down and up. $\endgroup$
    – Algebruh
    Apr 5 '21 at 12:56
  • $\begingroup$ No, I've checked and the third formula is just wrong. It's been pointed out on MSE before, for example in an answer to this question. $\endgroup$ Apr 5 '21 at 13:36
  • $\begingroup$ Sad...that would have been nice tho :) Thanks for checking! $\endgroup$
    – Algebruh
    Apr 5 '21 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.