34
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Just to confirm, this means each person must have at least one new neighbor for each seating, but they could sit next to the same person multiple times. Is that correct? $\endgroup$ – Arby Mar 4 '17 at 12:03
  • 3
    $\begingroup$ @Arby Yeah, you may sit next to the same person a number of times – just that you can't ever have the same pair for any person. $\endgroup$ – Parth Kohli Mar 4 '17 at 12:07
  • 4
    $\begingroup$ Not really... both neighbours may have sat with a person earlier, but not at the same time. So the pair must be new. $\endgroup$ – Parth Kohli Mar 4 '17 at 12:27
  • 3
    $\begingroup$ Ah, interesting. Seems like there are many extensions to the problem. Those are the good kind. $\endgroup$ – Arby Mar 4 '17 at 13:11
  • 3
    $\begingroup$ @n.m. I don't think your sequence is correct. You find $7$ for $6$ vertices? There are clearly 10. For example: (1, 2, 3, 4, 5, 6), (1, 3, 5, 4, 2, 6), (1, 4, 2, 5, 3, 6), (1, 5, 3, 2, 4, 6), (1, 2, 4, 3, 6, 5), (1, 3, 2, 6, 4, 5), (1, 4, 6, 3, 2, 5) , (1, 2, 6, 5, 3, 4), (1, 3, 6, 2, 5, 4), (1, 2, 5, 6, 4, 3) $\endgroup$ – Hitch Alisson Mar 21 '17 at 14:17
6
$\begingroup$

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.

  1. 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your last observation is great and deserves to be spelled out further. $\endgroup$ – David E Speyer Mar 23 '17 at 3:59
  • $\begingroup$ Thanks! I am doing it right now. $\endgroup$ – Aravind Mar 23 '17 at 4:00
  • $\begingroup$ There are some good ideas here, but also many things I don't understand. (1) Your connection between perfect $1$-factorization and the OP's question for an odd number of people. If you have $2m+1$ matchings of $K_{2m+1}$, then their unions give $\binom{2m+1}{2}$ Hamiltonian paths, not $\binom{2m}{2}$ as you would want. $\endgroup$ – David E Speyer Mar 23 '17 at 13:02
  • $\begingroup$ (2) Your construction joining $a/2$ to $b/2$ has the same problem -- if $n$ is prime, you make $\binom{n}{2}$ cycles, not $\binom{n-1}{2}$. One way to fix this would be to include an extra point called $\infty$, and join $a/2$ and $b/2$ to $\infty$, but this recovers the $p+1$ solution in my answer. $\endgroup$ – David E Speyer Mar 23 '17 at 13:04
  • $\begingroup$ (3) The number of cycles you have constructed in part 3 is $n\phi(n)/2$. This is NOT $\binom{n}{2} - o(n)$ as you claimed. For example, if $3$ divides $n$, then $\phi(n) \leq (2/3) n$ so this is $\leq (1/3) n^2$, not $n^2/2 - o(n)$. $\endgroup$ – David E Speyer Mar 23 '17 at 13:06
7
+100
$\begingroup$

$\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.

| cite | improve this answer | |
$\endgroup$

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.