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

combinatoricsgraph theory

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

Best Answer

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

Related Solutions

[Math] Simple graphs (edges, nodes etc.)

I agree with Brad on the intended interpretation of the question. This means, as he said, that there is only one graph with no edges; if you think of the entire top row of your picture as one graph, that’s it. It also means that each of the three one-edge graphs in your second row is missing a vertex. The first, for instance, should be

                       a *--------* b             * c

As Brad said, the three graphs in your bottom row are all the same graph, merely drawn differently. Thus, you should have a total of eight graphs, one with no edges, three with one edge each, three with two edges each, and one with three edges.

Now look at the hint in question (4), but apply it to these graphs: there are $3$ possible edges, $ab, bc$, and $ac$, and in any given graph on the vertex set $\{a,b,c\}$ each of these edges can be either present or absent. Thus, for each of the three edges you have a two-way choice when constructing a graph: keep the edge, or discard it. For instance, keeping $ab$ and discarding the other two yields the graph that I drew above. How many ways are there to make $3$ $2$-way choices? $2\cdot 2\cdot 2=2^3=8$, right? That’s why there are $8$ graphs on the vertex set $\{a,b,c\}$. Now try applying this logic to question (4).

Notice also that we could have counted the two-edge graphs on $\{a,b,c\}$ by asking how many ways there are to pick $2$ of the $3$ possible edges to keep. How many ways are there to pick $k$ things from a collection of $n$ different things? That idea should carry you through the rest of the questions.

Added in response to comments/questions: Yes, there are $\binom{n}2$ possible edges over $V_3$. Each pair of vertices is a possible edge, and from an $n$-element set you can make $\binom{n}2$ distinct pairs. To make a graph with vertex set $V_3$, you must choose to keep some subset of these $\binom{n}2$ possible edges. A collection of $\binom{n}2$ things has $2^{\binom{n}2}$ possible subsets, so there are $2^{\binom{n}2}$ possible graphs with vertex set $V_3$, not $2^n$. (This is the same mistake that you made in question (4).)

For question (8) you want to make graphs with $k$ edges. There are as many of these as there are ways to choose $k$ of the $\binom{n}2$ possible edges. This is not $\binom{n}k$; what is it?

[Math] Number of connected / disconnected / total graphs with V vertices of degree d or d – 1

Presumably the problem shouldn't get harder if we drop the possibility to have degree $d-1$ and just try to count the $d$-regular graphs on $v$ labeled vertices. The answers to this MO question say that no closed form is known for this, so I doubt you'll find one for your problem. They do give asymptotic results and potentially useful references, though. You might also want to take a look at the MathWorld article on regular graphs.

Regarding connected and disconnected graphs, note that quite generally whenever a property of graphs is such that a graph has the property if and only if all its connected components have the property, then the exponential generating functions $g(x)$ for the number of graphs with the property and $c(x)$ for the number of non-empty connected graphs with the property are related by $g(x) = \exp(c(x))$. Thus, if you can determine $g(x)$, which will generally be easier than determining $c(x)$ directly, you can get $c(x)$ as $\log g(x)$.