# Handshaking with no crossovers in minimum number of rounds: has this problem been studied?

I've met a group of 9 colleagues (PhD students), and when we came to handshake it was complicated as always to handshake everyone and avoid cross overs.

So one guy suggested (he was not serious about it) to study the problem of the minimum number of rounds for a circle of $n$ friends to handshake such that no crossovers occur. Of couse the minimum if we allow crossovers is $n-1$ rounds, because if we fix a person, then in each round he gets to shake hands with at most one other person. But there is a moment where the two guys next to him shake hands, and so he sits idle in that round.

The natural question is if there is a formula for the least number of rounds needed in this case, or at least lower bound lower than the trivial bound where each person gets to shake hands with all others while everyone else stands still waiting for him to finish.

I am not expecting a solution but rather hoping if this problem has been studied before. When I tried searching I ran into all sorts of homework problems like "if 534345 handshakes happened then how many people were there" ... I wasn't also sure of the search terms; I tried both "crossovers" and "intersection" but no avail.

Edit:

From the comments I realize that maybe more solid definition for the problem is needed. Here it goes:

There is a set $P$ of $n$ people positioned at the vertices of a regular $n$-gon. The goal is that after the "program" terminates, every person should have shook hands with every other person exactly once. By "shaking hands" we mean that two persons have a edge connecting them. The execution proceeds in rounds, such that at each round a person may be either "shaking hands" with another person, or doing nothing. A person $i$ who shook hands in some preceding round with a subset of people $J\subseteq (P-\{i\})$ will consider only the people he did not shake hands with yet $(P-(J\cup\{i\}))$ in the next round, by selecting one of them to shake hands with. The constraint is that at no round no two edges can intersect.

The question is to determine the minimum number of rounds needed to solve this problem ?

Also I would be interested in a special case where the edges are restricted to be "straight lines", rendering the constraint a little bit different from planar graph condition, to a more geometrical condition.

• Do they have to stand in a circle? If you had 4 people standing "in convex position" (that is, at the vertices of a convex quadrilateral), they'd need four rounds, since only one pair of diagonal opposites can shake at a time, but if they stand as a triangle with one in the middle they can do it in three rounds. – Gerry Myerson Aug 1 '11 at 1:24
• @Gerry Myerson: This is an interesting observation, but I assumed the circle because it can be easily generalized to $n$ people. The symmetry also makes it easier for distributed systems, since we wouldn't need leader election or further synchronization/consensus to make. – Mohammad Alaggan Aug 1 '11 at 1:27
• If that is a cross-over, then perhaps you have the solution for $n$ smaller than $4$ and have a lower bound for $n > 4$ because the complete graph with $n$ vertices is not planar. Although that bound seems kind of trivial. – Patrick Da Silva Aug 1 '11 at 1:30
• Hmm. Maybe I said something weird. Never mind. – Patrick Da Silva Aug 1 '11 at 1:34
• Note that in the solution I posted, all edges are straight lines. – Gerry Myerson Aug 1 '11 at 2:05

Yes, this has been considered before.

When I was a high school student, I've seen this problem in a mathematics problem solving seminar (problem 4). Unfortunately, there is no English version of the problem statements and solutions.

If you drop the non-crossing condition, then the fact that $n-1$ rounds are enough when $n$ is even is a special case of Baranyai's theorem. The case of odd $n$ follows easily, because then $n-1$ rounds are not enough (since no perfect matching exists) and $n$ are enough, because we can use the strategy for $n+1$ people and ignore the person number $n+1$.

Allowing non-straight connections is the same as allowing crossings and the above applies. Indeed, whatever matching you come up with, you can draw it with curves without any crossings. This is because you can draw the connections one by one and since the graph has no cycles, no person will ever get enclosed.

Peter Jackson's notes on the combinatorics of handshakes contains the description of the solution with crossings allowed and it also gives the non-crossing solution for $n$ odd on page 5.

The dissertation of Andreas Razen contains a similar problem with almost the same motivation. (See page 48.)

I don't know if it has been studied before, but I think this may be a solution for even $n=2m$.

Number the people around the circle from 1 to $2m$.

In round $j$, $1\le j\le m$, person $j$ shakes hands with person $j+1$, and all other handshakes are "parallel" to this (so, $j-1$ with $j+2$, $j-2$ with $j+3$, and so on - throughout, the labels are interpreted modulo $n$, as necessary). At the end of these $m$ rounds, everyone has shaken hands with everyone an odd number of people away.

In round $m+j$, $1\le j\le m$, $j$ shakes with $j+2$ and all other handshakes are parallel (so $j-1$ with $j+3$, $j-2$ with $j+4$, etc.). This handles all the pairs an even number of people apart. So the total is $2m$ rounds.

As noted in the problem statement, $2m-1$ rounds is impossible, so $2m$ is the answer.

EDIT: The odd case is even easier. In round $j$, person $j$ sits out while $j-1$ greets $j+1$, $j-2$ greets $j+2$, etc., again using $n$ rounds.

• Great. A solution for $n=2m-1$ is by inserting an "imaginary" person that when a person $a$ shakes hands with, $a$ sits idle instead. This would be an $n+1$ rounds solution. We don't know if an $n$ round solution exists for this case yet. – Mohammad Alaggan Aug 1 '11 at 2:17