5
$\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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Feb 17, 2015 at 18:03

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Feb 17, 2015 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
    Commented Feb 17, 2015 at 18:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .