Ben Efraim's lexicographic edge-isoperimetric conjecture for the transposition graph

About 12 years old · traced to

Let SnS_n be the symmetric group, and let TnT_n be its transposition graph. For A⊂Sn\mathcal{A} \subset S_n, write ∂A\partial \mathcal{A} for its edge-boundary in TnT_n. Let C\mathcal{C} be the initial segment of the lexicographic order on SnS_n having size ∣A∣|\mathcal{A}|. Ben Efraim's conjecture. For every A⊂Sn\mathcal{A} \subset S_n,

∣∂A∣≥∣∂C∣.|\partial \mathcal{A}| \geq |\partial \mathcal{C}|.

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

Never refreshed

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.