Timeline for Girth of the symmetric group
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2018 at 17:09 | comment | added | Jean Raimbault | Unfortunately there seems to be a gap in the paper Andreas Thom cites, see arxiv.org/pdf/1706.09972.pdf by Sean Eberhard (which gives a lower bound of $n^{1/3}$) | |
| S Jun 8, 2017 at 14:35 | history | bounty ended | CommunityBot | ||
| S Jun 8, 2017 at 14:35 | history | notice removed | CommunityBot | ||
| Jun 5, 2017 at 18:45 | answer | added | Ian Agol | timeline score: 5 | |
| Jun 2, 2017 at 12:12 | comment | added | Mikael de la Salle | @AndreasThom: thank you for the reminder, I keep making the same mistake. | |
| Jun 2, 2017 at 12:08 | comment | added | Andreas Thom | @MikaeldelaSalle: The order can be as large as $\exp((n\log(n))^{1/2})$. Take a disjoint union of prime cycles $(p_1)...(p_k)$ such that $p_1+\cdots+p_k \sim n$. Then this works for the first primes up to roughly $(n\log(n))^{1/2}$ and then $p_1\cdot \cdots \cdot p_k$ (the order of the permutation) is roughly $\exp((n\log(n))^{1/2})$. This was first observed by Landau. | |
| Jun 2, 2017 at 11:48 | comment | added | Mikael de la Salle | Andreas, I am puzzled about your guess that the maximal girth is bounded below by $\Omega(n \log n)$: isn't the girth always less than the order of $\sigma$ and $\tau$, that is less than $n$? | |
| S May 31, 2017 at 13:00 | history | bounty started | Andreas Thom | ||
| S May 31, 2017 at 13:00 | history | notice added | Andreas Thom | Draw attention | |
| May 30, 2017 at 15:13 | comment | added | Andreas Thom | @DenisT.: I think that this result on the maximal element order is already due to Landau. I would be interested to see the details of your approach! | |
| May 30, 2017 at 13:53 | comment | added | Denis T | By theorem of W. Miller, asymtotic exponent of symmetric group is $exp((n \mathrm{ln}n)^{1/2})$, so choosing generators of maximal order and then considering upper bound for fixed points of their products (product of elements with well-mixed cycle types have in general more than half points not fixed) you probably can obtain something. | |
| May 29, 2017 at 10:53 | comment | added | Shahrooz | @YCor you are right, I did a mistake. | |
| May 29, 2017 at 10:51 | comment | added | YCor | @ShahroozJanbaz the graph is $2|A|$-regular, i.e. 4-regular. You're forgetting inverses. | |
| May 29, 2017 at 10:51 | comment | added | YCor | Side note: the girth is meant to be the smallest length of a nontrivial element in the kernel of the canonical map from the free group on $(\sigma,\tau)$ to Sym(n). (In particular, for it to match with the Cayley graph girth, one needs to use a pair of edges if one generator were of order 2, to force the girth to be 2). | |
| May 29, 2017 at 10:50 | comment | added | Shahrooz | @YCore since $A=\{\sigma,\tau\}$ generates $S_{2k-1}$, the graph is connected and is $|A|$-regular, i.e, 2-regular, so it is a cycle. | |
| May 29, 2017 at 10:46 | comment | added | YCor | @ShahroozJanbaz this has bounded girth! Indeed, $[\sigma,\tau]^3=1$, which is a cycle of length 12. | |
| May 29, 2017 at 10:44 | history | edited | Andreas Thom | CC BY-SA 3.0 |
deleted 4 characters in body
|
| May 29, 2017 at 10:33 | comment | added | Shahrooz | Let $\sigma=(1,\ldots,k)$ and $\tau=(k,k+1,\ldots,2k-1)$. If $k$ be an even integer, the set $\{\sigma,\tau\}$ generates $S_{2k-1}$ and so the Cayley graph $Cay(S_{2k-1},\{\sigma,\tau\})$ is a cycle which has the maximum girth. | |
| May 29, 2017 at 9:46 | history | asked | Andreas Thom | CC BY-SA 3.0 |