Cliques en el grafo de Cayley en $n$ -ciclos

Question

Dejemos que $S\subset S_n$ sea el conjunto de todos los $n$ -ciclos. Quiero saber si el grafo de Cayley $(S_n,S)$ tiene grandes subgrafos densos. Espero que no tenga un tamaño superpolinómico y $1-o(1)$ subgrafos densos.

Sin embargo, un buen punto de partida puede ser la siguiente pregunta:

¿Cuál es el tamaño de la mayor camarilla (y biclica) de $(S_n,S)$ ?

Como $(S_n,S)$ es un subgrafo del polítopo de Birkhoff $B_n$ un límite en el tamaño de la camarilla de $B_n$ también puede ser útil. Me parece que esta pregunta estrechamente relacionados, pero sin límites en términos de $n$ se dieron allí.

Otro resultado relacionado que encuentro es sobre el número de independencia de $B_n$ , demostrado en Kane, Lovett y Rao :

El número de independencia $\alpha(B_n)$ satisface $n!/4^n\leq\alpha(B_n)\leq n!/2^{(n-4)/2}$ .

Answer 1

Ilya escribió correctamente en los comentarios que una camarilla no puede ser mayor que $n$ y también ese tamaño $n$ no es posible cuando $n$ es par (excepto $n=2$ ).

Cliques de tamaño exacto $n$ se estudian bajo el nombre de cuadrados latinos pan-hamiltonianos . Es un problema no resuelto para el que $n$ existen. En este documento Ian Wanless conjetura que existen para todos los impar $n$ y señala que la conjetura se ha demostrado por construcción hasta $n=49$ . No sé si ese valor se ha incrementado desde entonces.