Ben Efraim's lexicographic edge-isoperimetric conjecture for the transposition graph
Let be the symmetric group, and let be its transposition graph. For , write for its edge-boundary in . Let be the initial segment of the lexicographic order on having size . Ben Efraim's conjecture. For every ,
This would give an edge-isoperimetric inequality for the transposition graph that is sharp for every set size; the source provides no resolution, so the conjecture remains open.
References
Primary source
David Ellis, Yuval Filmus and Ehud Friedgut, “Low-degree Boolean functions on S_n, with an application to isoperimetry”, arXiv:1511.08694 (2017).
Additional references
2 papers in this index state this conjecture (2014–2015). The statement above is taken from the most recent of them; the others are arXiv:1409.4542.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.