Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

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

share|improve this answer
    
Yes, thank you. I see now what I really want to know is how to compute the minimum number of edges in a complete k-partite graph. –  Geoffrey Critzer May 24 at 18:53
    
Great, yeah, that's the more interesting question. I'll update my answer to include the full minimization argument. –  Peter Woolfitt May 24 at 18:55
    
Your last sentence: "In particular, if N is congruent to h mod r. I think you mean if N is congruent to h mod k. –  Geoffrey Critzer May 25 at 18:20
    
The second N in your formula should be k not N. –  Geoffrey Critzer May 25 at 18:22
1  
Transpose[ Table[nn = 10; PadLeft[Table[ Binomial[n, 2] - Mod[n, k] Binomial[Floor[n/k] + 1, 2] - (k - Mod[n, k]) Binomial[Floor[n/k], 2], {n, k, nn}], nn + 1], {k, 1, 10}]] // Grid –  Geoffrey Critzer May 25 at 18:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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