$n$ people sitting on a circular table without repeating neighbour-sets

Question

I made this problem up and it's been bothering me ever since.

We're organising team activities in our company for the next few days. Our team consists of $n$ people seated on a circular table. To spice it up, we plan to do it in such a way that no single person has to sit with the same pair of people on any two given days. What's the longest period of time for which this can be done, without running out of arrangements?

The upper-bound to this is, of course, $\binom{n-1}2$, because if we pick a member and find the number of ways to seat neighbours around him, we see that it is $\binom{n-1}2$. Since this pair of neighbours can only be seated once on that day, by pigeonhole (or whatever it's called) we cannot pick any more combinations after $\binom{n-1}2$ days. Roughly sketching it for $n = 3, 4, 5$, it's actually equal to the aforementioned upper bound, so that's a nice fact.

But otherwise, I've gone off to tangents that will probably not be relevant to this discussion, and that's all the work I could come up with.

Answer 1

I prove the following:

1. The OP's claim follows from the perfect-1-factorization conjecture: $K_{2m}$ can be decomposed into $2m-1$ perfect matchings such that the union of any two matchings forms a Hamiltonian cycle of $K_{2m}$.

An equivalent version is that $K_{2m-1}$ can be decomposed into $2m-1$ near-perfect matchings such that the union of any two near-perfect matchings forms a Hamiltonian path. Here, a near perfect matching is a collection of edges which induce a matching that covers all but one vertex.

2. If $n$ is even, then we can make $\dfrac{(n-1)\varphi(n-1)}{2}$ configurations, where $\varphi$ is the Euler totient function. [Corrected from previous wrong claims.]

Proof of 1: Given the conjecture for a particular even $n$, we take the union of every pair of matchings to be the configuration.

Proof of 2: Let $N=n-1$. We identify one person as $N$ and the others with $\{0,1,\ldots,N-1\}$ and work in arithmetic modulo $N$.

For each pair $(a,b)$ with $0 \leq a< b < N$, we define a configuration $C_{a,b}$ in which the neighbors of $x$ are $a-x$ and $b-x$. Also notice that when $N$ is odd, both $a/2$ and $b/2$ really have only one neighbor, therefore in this case, we make them both adjacent to $N$ in $C_{a,b}$ (idea of David Speyer).

We have considered the union of the two matchings $\{(x,a-x)\}$ and $\{(x,b-x)\}$. In general, this union need not be a hamiltonian cycle (which we want a configuration to be).

Claim: If $gcd(a-b,N)=1$, then $C_{a,b}$ is a valid cyclic permutation.

To prove the claim, let's consider the following edge coloring of the complete graph $K_N$: the edge $\{x,y\}$ is labeled by $x+y$. Notice that this is a proper edge coloring, i.e. no two edges get the same color. Now consider the subgraph induced by two color classes, $a,b$. Suppose that this subgraph has a cycle, say $x_1,x_2,\ldots,x_{2k}$. Then $x_1-x_3=a-b,\ldots,x_{2k-1}-x_1=a-b$. Adding these up, we get: $k(a-b)=0$. Since $k<N$, we must have $gcd(a-b,N)>1$. This shows that when $gcd(a-b,N)=1$, the union of the two color classes $a,b$ forms a Hamiltonian path between $a/2$ and $b/2$.

Counting: The number of configurations is $\sum_{gcd(d,N)=1} (N-d)=N\varphi(N)/2$.

Answer 2

$\def\FF{\mathbb{F}}\def\PP{\mathbb{P}}$I can achieve the bound $\binom{n-1}{2}$ if $n=q+1$ for a prime power $q$.

Outline of method: Suppose that $X$ is a set of size $n$ and $G$ is a group acting on $X$ in a sharply three transitive manner. This means that, is $(x_1, x_2, x_3)$ and $(y_1, y_2, y_3)$ are two ordered triples of distinct elements of $G$, there is precisely one $g \in G$ with $g(x_i)=y_i$ for $i=1$, $2$, $3$. (So, in particular, we have $|G| = n(n-1)(n-2)$.) Suppose furthermore that there is an element $\gamma$ in $G$ which acts by an $n$-cycle on $X$, and $\gamma$ is conjugate to $\gamma^{-1}$.

Then I claim $n$ is achievable. Let $C \subset G$ be the conjugacy class of $\gamma$. We note that the only permutations in $S_n$ which commute with an $n$-cycle are powers of that $n$-cycle, so $Z(\gamma) = \langle \gamma \rangle$ and the size of the conjugacy class $C$ is $|G|/|Z(\gamma)| = n(n-1)(n-2)/n=(n-1)(n-2)$.

I claim that, for any distinct elements $y_1$, $y_2$, $y_3$ in $X$, there is a unique $\delta \in C$ with $\delta(y_1) = y_2$ and $\delta(y_2) = y_3$. We first see that there is at least one $\delta$: Fix $x_1 \in X$, define $x_2 = \gamma(x_1)$ and $x_3 = \gamma(x_2)$, and let $h \in G$ be such that $h(x_i) = y_i$. Then $\delta = h \gamma h^{-1}$ does the job. But $|C| = (n-1) (n-2)$ and each $\delta \in C$ gives rise to $n$ triples $(y_1, y_2, y_3)$ with $\delta(y_1) = y_2$, $\delta(y_2) = y_3$. So, if each triple occurs at most once, then each triple occurs exactly once.

We have shown that the elements of $C$ are $(n-1)(n-2)$ oriented $n$-cycles, with each $y_1 \to y_2 \to y_3$ occurring in exactly one. But also, we assumed $\gamma$ conjugate to $\gamma^{-1}$, so for every cycle in $C$ its reverse is also in $C$. Identifying these, we get $\binom{n-1}{2}$ unoriented cycles, where for each $y_2$, and each pair of neighbors $y_1$, $y_3$, there is exactly one cycle where they occur.

Details Take $X = \PP^1(\FF_q)$ and $G = PGL_2(\FF_q)$ with the obvious action. It is well known that $G$ is sharply triply transitive. Choose an identification of $(\FF_q)^2$ with the field $\FF_{q^2}$, choose a generator $\theta$ for the cyclic group $\FF_{q^2}^{\times}$ and let $\gamma \in GL_2(\FF_q)$ be the matrix of multiplication by $\theta$. Then the image of $\gamma$ in $PGL_2(\FF_q)$ has order $q+1$. Moreover, in $PGL_2(\FF_q)$, every element is conjugate to its inverse. This proves the claim. $\square$.

Zassenhaus classified the sharply triple transitive permutation groups and, for all of them, $|X|=q+1$ for a prime power $q$. So there aren't any other $n$ achievable in this way.