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

  • 1
    $\begingroup$ 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. $\endgroup$ – Ilya Bogdanov Nov 16 '18 at 19:29
  • $\begingroup$ This argument shows also that a subgraph on $\Omega(n)$ vertices cannot have edge density $1-o(1)$. $\endgroup$ – Ilya Bogdanov Nov 16 '18 at 19:34
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Thank you. Are there results on bicliques known? $\endgroup$ – Willard Zhan Nov 17 '18 at 17:08
  • $\begingroup$ @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. $\endgroup$ – Brendan McKay Nov 18 '18 at 13:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.