$n$ personas sentadas en una mesa circular sin repetir conjuntos de vecinos

Question

Hice este problema y desde entonces me ha estado molestando.

Estamos organizando actividades en equipo en nuestra empresa para los próximos días. Nuestro equipo consta de $n$ personas sentadas en una mesa circular. Para animar las cosas, planeamos hacerlo de tal manera que ninguna persona tenga que sentarse con la misma pareja de personas en dos días consecutivos. ¿Cuál es el período de tiempo más largo para el cual esto se puede hacer, sin quedarnos sin arreglos?

El límite superior para esto es, por supuesto, $\binom{n-1}2$, porque si elegimos a un miembro y encontramos el número de formas de sentar a sus vecinos alrededor de él, vemos que es $\binom{n-1}2$. Dado que esta pareja de vecinos solo puede sentarse una vez en ese día, por la paradoja del cumpleaños (o como sea que se llame) no podemos elegir más combinaciones después de $\binom{n-1}2$ días. Haciendo un boceto aproximado para $n = 3, 4, 5$, en realidad es igual al límite superior mencionado, así que eso es un dato interesante.

Pero de lo contrario, me he ido por tangentes que probablemente no serán relevantes para esta discusión, y ese es todo el trabajo que se me ocurrió.

Answer 1

$\def\FF{\mathbb{F}}\def\PP{\mathbb{P}}$Puedo lograr el límite $\binom{n-1}{2}$ si $n=q+1$ para un primo $q$.

Esquema del método: Supongamos que $X$ es un conjunto de tamaño $n$ y $G$ es un grupo que actúa en $X$ de manera marcadamente triple transitiva. Esto significa que, si $(x_1, x_2, x_3)$ y $(y_1, y_2, y_3)$ son dos tripletas ordenadas de elementos distintos de $G$, hay precisamente un $g \in G$ con $g(x_i)=y_i$ para $i=1$, $2$, $3. (Entonces, en particular, tenemos $|G| = n(n-1)(n-2)$.) Supongamos además que hay un elemento $\gamma$ en $G$ que actúa con un ciclo de tamaño $n$ en $X$, y $\gamma$ es conjugado a $\gamma^{-1}$.

Luego afirmo que $n$ es alcanzable. Sea $C \subset G$ la clase de conjugación de $\gamma$. Notamos que las únicas permutaciones en $S_n$ que conmutan con un ciclo de tamaño $n$ son potencias de ese ciclo de tamaño $n$, por lo que $Z(\gamma) = \langle \gamma \rangle$ y el tamaño de la clase de conjugación $C$ es $|G|/|Z(\gamma)| = n(n-1)(n-2)/n=(n-1)(n-2)$.

Afirmo que, para cualquier elementos distintos $y_1$, $y_2$, $y_3$ en $X$, hay un único $\delta \in C$ con $\delta(y_1) = y_2$ y $\delta(y_2) = y_3$. Primero vemos que hay al menos un $\delta$: Fijemos $x-1 \in X$, definamos $x_2 = \gamma(x_1)$ y $x_3 = \gamma(x_2)$, y sea $h \in G$ tal que $h(x_i) = y_i$. Entonces $\delta = h \gamma h^{-1}$ hace el trabajo. Pero $|C| = (n-1)(n-2)$ y cada $\delta \in C$ da lugar a $n$ tripletes $(y_1, y_2, y_3)$ con $\delta(y_1) = y_2$, $\delta(y_2) = y_3$. Así que si cada triplete ocurre a lo sumo una vez, entonces cada triplete ocurre exactamente una vez.

Hemos demostrado que los elementos de $C$ son $(n-1)(n-2)$ ciclos orientados de tamaño $n$, con cada $y_1 \to y_2 \to y_3$ ocurriendo exactamente una vez. Pero también, asumimos que $\gamma$ es conjugado a $\gamma^{-1}$, así que para cada ciclo en $C$, su inverso también está en $C$. Identificando estos, obtenemos $\binom{n-1}{2}$ ciclos no orientados, donde para cada $y_2$, y cada par de vecinos $y_1$, $y_3$, hay exactamente un ciclo donde ocurren.

Detalles Tomemos $X = \PP^1(\FF_q)$ y $G = PGL_2(\FF_q)$ con la acción obvia. Es bien sabido que $G$ es marcadamente triple transitivo. Elige una identificación de $(\FF_q)^2$ con el campo $\FF_{q^2}$, elige un generador $\theta$ para el grupo cíclico $\FF_{q^2}^{\times}$ y deja que $\gamma \in GL_2(\FF_q)$ sea la matriz de multiplicación por $\theta$. Entonces la imagen de $\gamma$ en $PGL_2(\FF_q)$ tiene orden $q+1$. Además, en $PGL_2(\FF_q)$, cada elemento es conjugado a su inverso. Esto demuestra la afirmación. $\square$.

Zassenhaus clasificó los grupos de permutaciones marcadamente triple transitivas y, para todos ellos, $|X|=q+1$ para un primo $q$. Por lo tanto, no hay otros valores de $n$ alcanzables de esta manera.

Answer 2

Demuestro lo siguiente:

1. La afirmación del OP sigue de la conjetura de factorización perfecta-1: $K_{2m}$ puede ser descompuesto en $2m-1$ emparejamientos perfectos de manera que la unión de cualquier par de emparejamientos forme un ciclo Hamiltoniano de $K_{2m}.

Una versión equivalente es que $K_{2m-1}$ puede ser descompuesto en $2m-1$ emparejamientos cercanamente perfectos de manera que la unión de cualquier par de emparejamientos cercanamente perfectos forme un camino Hamiltoniano. Aquí, un emparejamiento cercanamente perfecto es una colección de aristas que inducen un emparejamiento que cubre todos los vértices excepto uno.

2. Si $n$ es par, entonces podemos hacer $\dfrac{(n-1)\varphi(n-1)}{2}$ configuraciones, donde $\varphi$ es la función totiente de Euler. [Corregido de afirmaciones previas incorrectas.]

Prueba de 1: Dada la conjetura para un $n$ par específico, tomamos la unión de cada par de emparejamientos como la configuración.

Prueba de 2: Sea $N=n-1$. Identificamos a una persona como $N$ y a los demás con $\{0,1,\ldots,N-1\}$ y trabajamos en aritmética módulo $N$.

Para cada par $(a,b)$ con $0 \leq a< b < N$, definimos una configuración $C_{a,b}$ en la que los vecinos de $x$ son $a-x$ y $b-x$. También notamos que cuando $N$ es impar, tanto $a/2$ como $b/2$ realmente solo tienen un vecino, por lo tanto, en este caso, los hacemos ambos adyacentes a $N$ en $C_{a,b}$ (idea de David Speyer).

Hemos considerado la unión de los dos emparejamientos $\{(x,a-x)\}$ y $\{(x,b-x)\}$. En general, esta unión no tiene por qué ser un ciclo hamiltoniano (lo cual es lo que queremos que una configuración sea).

Afirmación: Si $gcd(a-b,N)=1$, entonces $C_{a,b}$ es una permutación cíclica válida.

Para probar la afirmación, consideremos la siguiente coloración de aristas del grafo completo $K_N$: la arista $\{x,y\}$ está etiquetada por $x+y$. Notemos que esta es una coloración de aristas adecuada, es decir, ninguna dos aristas tienen el mismo color. Ahora consideremos el subgrafo inducido por dos clases de colores, $a,b$. Supongamos que este subgrafo tiene un ciclo, digamos $x_1,x_2,\ldots,x_{2k}$. Luego $x_1-x_3=a-b,\ldots,x_{2k-1}-x_1=a-b$. Sumándolos, obtenemos: $k(a-b)=0$. Como $k1$. Esto muestra que cuando $gcd(a-b,N)=1$, la unión de las dos clases de colores $a,b$ forma un camino Hamiltoniano entre $a/2$ y $b/2$.

Conteo: El número de configuraciones es $\sum_{gcd(d,N)=1} (N-d)=N\varphi(N)/2$.