# Cliques in Cayley graph on $n$-cycles

Let $$S\subset S_n$$ be the set of all $$n$$-cycles. I want to know if the Cayley graph $$(S_n,S)$$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $$1-o(1)$$ dense subgraphs.

However, one good starting point maybe the following question:

What is the size of the largest clique (and biclique) of $$(S_n,S)$$?

As $$(S_n,S)$$ is a subgraph of the Birkhoff polytope graph $$B_n$$, a bound on the clique size of $$B_n$$ might be also helpful. I find this question closely related, but no bounds in terms of $$n$$ were given there.

Another related result I find is on the independence number of $$B_n$$, proved in Kane, Lovett and Rao:

The independence number $$\alpha(B_n)$$ satisfies $$n!/4^n\leq\alpha(B_n)\leq n!/2^{(n-4)/2}$$.

• If $n$ is prime, then tge powers of one cycle form a largest size clique. Ondeed, among $n+1$ permutations, two send $1$ to the same element, hence they dp not differ by an $n$-cycle. – Ilya Bogdanov Nov 16 '18 at 19:29
• This argument shows also that a subgraph on $\Omega(n)$ vertices cannot have edge density $1-o(1)$. – Ilya Bogdanov Nov 16 '18 at 19:34
• On the other hand, if $n$ is even, then any $n$-cycle is odd, hence the graph is bipartite, and there is no triangle in it. – Ilya Bogdanov Nov 16 '18 at 21:50

Ilya correctly wrote in the comments that a clique cannot be larger than $$n$$, and also that size $$n$$ is not possible when $$n$$ is even (except $$n=2$$).

Cliques of size exactly $$n$$ are studied under the name of pan-Hamiltonian latin squares. It is an unsolved problem for which $$n$$ they exist. In this paper Ian Wanless conjectures that they exist for all odd $$n$$, and notes that the conjecture has been proved by construction up to $$n=49$$. I don't know if that value has been increased since then.

• Thank you. Are there results on bicliques known? – Willard Zhan Nov 17 '18 at 17:08
• @WillardZhan Not that I know of, but I'm not a specialist in this subject. Ian's email is easy to locate, you should ask him. – Brendan McKay Nov 18 '18 at 13:05