AN ISOPERIMETRIC INEQUALITY FOR CONJUGATION-INVARIANT SETS IN THE SYMMETRIC GROUP

作者：Atzmon Neta^*; Ellis David; Kogan Dmitry

来源：Israel Journal of Mathematics, 2016, 212(1): 139-162.

DOI：10.1007/s11856-016-1296-7

We prove an isoperimetric inequality for conjugation-invariant sets of size k in Su, showing that these necessarily have edge-boundary considerably larger than some other sets of size k (provided k is small). Specifically, let T-n denote the Cayley graph on S-n generated by the set of all transpositions. We show that if A subset of S-n is a conjugation-invariant set with vertical bar A vertical bar = pn! <= n!/2, then the edge-boundary of A in T-n has size at least
c . log2(i/p)/log(2)log(2) (2/p) . n . vertical bar A vertical bar
where c is an absolute constant. (This is sharp up to an absolute constant factor, when p = Theta(1/s!) for any s is an element of {1, 2, ... , n}.) It follows that if p = n(-Theta(1)), then the edge-boundary of a conjugation-invariant set of measure p is necessarily a factor of Omega (log n/log log n) larger than the minimum edge-boundary over all sets of measure p.

• 出版日期2016-5