4
$\begingroup$

The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different in each seating arrangement?"

Here is a snap solution: For seating arrangements of $N$ people consider a directed graph with $N$ vertices and two opposite arcs connecting every pair of distinct vertices. Every hamiltonian cycle in that graph corresponds to a seating arrangement, where a directed edge corresponds to ''sitting to the left''. Call two hamiltonian cycles "intersecting" if they share a directed edge. The problem boils down to finding the maximal set of pairwise non-intersecting hamiltonian cycles. Since every vertex has $N-1$ outgoing edges the upper bound is $N-1$.

And here comes the error: Since hamiltonian cycles don't break a complete graph into disconnected components, we conjectured that the same is true for a set of non-intersecting hamiltonian cycles and therefore the above upper bound is exact.

However, a small experiment with $N=4$ demonstrates that the above conjecture is not true: removing any 2 hamiltonian cycles from a complete directed graph with 4 nodes breaks it into 2 disconnected components with 2 nodes each. Therefore the answer for $N=4$ is $2$, not $3$, and the above arguments leads only to an upper bound rather than an exact answer.

Thus the question: how does one compute the maximum number of non-intersecting hamiltonian cycles in a complete directed graph that can be removed before the graph becomes disconnected?

$\endgroup$
  • $\begingroup$ Another snap solution: for 5 people and person A , any 5 arrangements must have at least one person P appearing at least twice on A's left. $\endgroup$ – The Masked Avenger Feb 17 '15 at 18:03
10
$\begingroup$

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.

What is the maximum number of edge-disjoint directed Hamiltonian cycles of $K_{n}^{*}$?

For $n=2k+1$ odd, it is an old theorem of Walecki that $K_n$ can be decomposed into $k$ Hamiltonian cycles, and hence $K_n^*$ can be decomposed into $2k$ directed Hamiltonian cycles.

For $n=2k$ even, you are right to note that for $n=4$ we cannot achieve the upper bound of $n-1.$ One can also check that we cannot achieve the upper bound for $n=6$. However, Tilson proved that for even $n \geq 8$, $K_n^*$ can de decomposed into $n-1$ directed Hamiltonian cycles.

This completely answers your question. Namely, $n=4$ and $n=6$ are the only exceptions.

$\endgroup$
  • $\begingroup$ Even though there is a graeco-latin square of order 4, I wonder if there is a connection this problem has with G-L squares (or with the symmetric group S_6 having an unusual automrphism group). $\endgroup$ – The Masked Avenger Feb 17 '15 at 18:09
  • $\begingroup$ Interesting. I am not sure if there is a connection. My first reaction is that this is just an instance of the Strong Law of Small Numbers (en.wikipedia.org/wiki/Strong_Law_of_Small_Numbers), but there may be something deeper lurking. $\endgroup$ – Tony Huynh Feb 17 '15 at 18:14

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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