LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY

Abstract: We prove that Boolean functions on

S_{n}

, whose Fourier transform is highly concentrated on irreducible representations indexed by partitions of

n

whose largest part has size at least

n - t

, are close to being unions of cosets of stabilizers of

t

-tuples. We also obtain an edge-isoperimetric inequality for the transposition graph on

S_{n}

which is asymptotically sharp for subsets of

S_{n}

of size

n! / e x t r m p o l y (n)

, using eigenvalue techniques. We then combine these two results to obtain a sharp edge-isoperimetric inequality for subsets of

S_{n}

of size

(n - t)!

, where

n

is large compared to

t

, confirming a conjecture of Ben Efraim in these cases.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY