What is the maximum number of edges in a complete multipartite graph?

Question

The concept of complete bipartite graphs can be generalized to define the complete multipartite graph $K(r_1,r_2,...,r_k)$. It consists of $k$ sets of vertices each with cardinality $r_i$ for $i$ in $\{1,2,\ldots,k\}$ where all possible "interest" edges are present but no "intraset" edges are present.

For bipartite graphs I have Mathematica code: Table[Floor[n/2] Ceiling[n/2], {n, 0, 10}] {0, 0, 1, 2, 4, 6, 9, 12, 16, 20, 25}

for tripartite graphs I have:

f[n_] := Which[Mod[n, 3] == 0, 3 (n/3)^2, Mod[n, 3] == 1, Floor[n/3]^2 + 2 Ceiling[n/3] Floor[n/3], Mod[n, 3] == 2, Ceiling[n/3]^2 + 2 Ceiling[n/3] Floor[n/3]]; Table[f[n], {n, 0, 10}] {0, 0, 1, 3, 5, 8, 12, 16, 21, 27, 33}

In neither case am I convinced that I am correct. It just seems intuitive that the sets must be (as nearly as possible) the same size. How can I generalize for larger k?

This question is an exercise in "Combinatorics and Graph Theory" Harris,Herst,Mossinghoff. page 16.

I read and understood the solution given by Kaya in another post: $n^2\frac{k-1}{2k}$ but this is only true when $n$ is a multiple of $k$. I want to be able to write a code in Mathematica for any $k$ and any $n$.

Answer 1

Forget the coding, we can solve it explicitly!

Let $N=r_1+r_2+...r_k$ be the number of vertices in the graph. Now, for each $r_i$-partite set, we are blocked from making $r_i\choose 2$ edges. However, this is the only restriction on edges, so the number of edges in a complete multipartite graph $K(r_1,\ldots, r_k)$ is just

$|E|={N\choose2}-\sum\limits_{i=1}^k{r_i\choose 2}$

Hence, if you want to $\textit{maximize}$ the number of edges for a given $k$, you can just choose each sets such that $r_i=1\forall i$, which gives you the maximum $N\choose 2$.

If on the other hand you want to $\textit{minimize}$ the number of edges for a given $k$, we can use a little switching argument to show that the minimum occurs when all the $r_i$s are as near to $\frac{N}{k}$ as possible.

Here's the switching argument: Let $r=\lfloor \frac{N}{k}\rfloor$. Assume for the sake of contradiction that there exist $r_i$ and $r_j$ such that $r_j-r_i\geq 2$ in a $k$-partite graph $M$ with a minimum number of edges. Let $|M|$ denote the number of edges in $M$. Consider now $M'$ which we create from $M$ by taking a vertex $x$ in the $r_j$ set and adding it to the $r_j$ set. This switch adds $r_j-1$ edges and gets rid of $r_i$ edges. Hence $|M'|=|M|+r_j-1-r_i\leq |M|-1$ Hence we have a contradiction. This means that the sizes of two sets cannot differ in size by more than $1$. Hence a $k$-partite graph of minimum size must must have $r_i\in\{r,r+1\}$ for all $i\in\{1,2,\ldots,k\}$. In particular, if $N\equiv h \mod k$. Then the minimum number of edges of a $k$-partite graph is

$|E|={N\choose 2}-h{r+1\choose 2}-(k-h){r \choose2}$.

Answer 2

In order to avoid the switching argument, we can use a Hölder's inequality Corollary:

Let $x \in \mathbb{R^n}, \|x\|_{p} \leq n^{\frac{1}{p}-\frac{1}{q}}·\|x\|_{q} $

For a proof, click here.

So for a graph $G$ with $|V(G)|=n=r_1+r_2+...r_k$ : $$|E(G)| \leq \frac{n·(n-1)}{2} − \sum_{i=1}^{k}\frac{r_i(r_i-1)}{2}$$

We have: $$\sum_{i=1}^{k}\frac{r_i(r_i-1)}{2}=\sum_{i=1}^{k}\frac{r_i^2}{2}-\frac{n}{2}= \frac{\|r\|_2}{2}^2-\frac{n}{2}\geq \frac{(k^\frac{-1}{2}·\|r\|_1)^2}{2} -\frac{n}{2}=\frac{n^2}{2k}-\frac{n}{2}$$

So: $$|E(G)| \leq \frac{n·(n-1)}{2}-\frac{n^2}{2k}+\frac{n}{2}=\frac{n^2(k-1)}{2k}$$