The exact diameter of the symmetric group 𝑆𝑛 with LRX generators
Source: hexagonmath.org/abs/2611.00333v1
We consider the undirected Cayley graph of the symmetric group 𝑆𝑛 with respect to the cyclic shift 𝐿, its inverse 𝑅, and the transposition 𝑋 of the first two positions. We prove that its diameter is given by 𝑛(𝑛 − 1)/2 for every 𝑛 ≥ 4, thus settling a conjecture open since at least 2011. This is done by separately establishing sharp upper and lower bounds, invoking a variety of combinatorial and group-theoretic arguments which leave a finite set of special cases that are verified in the accompanying C++ code. We also provide a Lean formalization of the results.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00333
curl -X POST /api/v1/records/hexagon/2611.00333/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00333/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'