Delphi.science

Exact directed L/X diameter of the symmetric group

S. Uskov, A. Chervov, F. Levkovich-Maslyuk, I. Litvak, A. Smolensky, A. Soibelman

Palomar Registrypalomar/PALOMAR-2026-11-02-000017Nov 2, 2026math.COscore 0

For every n >= 5, the directed Cayley graph of the symmetric group S_n with unit-cost generators L = (0 1 ... n-1) and X = (0 1) has diameter (3n^2 - 8n + 12)/4 for even n and (3n^2 - 8n + 9)/4 for odd n. The formalization proves matching upper and lower bounds, and the existence of a literal L/X word within the sharp bound between every ordered pair of permutations. The independent statement takes the maximum of minimum word lengths over all ordered pairs. No inverse shift is included among the unit-cost moves.

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-02-000017
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-02-000017/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-02-000017/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'