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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 18, 2018 at 13:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .