How do I manage $13$ people to be interacted with each other in the minimum possible time?

Question

I have arranged an interaction meeting of $13$ people. All I want is these $13$ people to interact with each other. As in, every person must be interacting with remaining $12$ people. How do I manage this in the minimum possible time?

Answer 1

This problem can be restated in graph-theoretical terms:

What is the minimal number of matchings $K_{13}$ can be decomposed into?

$K_{13}$ has 78 edges and a maximum matching in it has six edges, so we need at least 13 matchings.

We can find such a decomposition. Labelling the people $0,1,\dots,12$, round 0 has the following pairings: $$8\leftrightarrow9\tag1$$ $$10\leftrightarrow12\tag2$$ $$2\leftrightarrow5\tag3$$ $$3\leftrightarrow7\tag4$$ $$1\leftrightarrow6\tag5$$ $$4\leftrightarrow11\tag6$$ and $0$ has a "bye". Round $n$ ($0\le n\le12$) features the same pairings, only that $n$ is added to the numbers of all people and the result is taken modulo 13 (so for example $11\leftrightarrow0$ in round 1).

The bracketed numbers to the right of the pairings above are the distances between labels of the people in each pair, and they form a set of all distinct (unsigned) non-zero distances possible with 13 people involved. There are 13 of each distance in a labelled $K_{13}$, so the union of the pairings in all 13 rounds has 78 edges in total – proving that this is a decomposition of $K_{13}$ into the minimum possible number of matchings.

Answer 2

This is the same as teams playing in a tournament. It will take 13 rounds for all teams to play all possible matches, or, in your case, to perform all possible interactions. The total number of interactions is 78.