4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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, 2018 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, 2018 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, 2018 at 21:50

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. Are there results on bicliques known? $\endgroup$
    – Wei Zhan
    Nov 17, 2018 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, 2018 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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