Geodesic
LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY
Forum of Mathematics, Sigma, Tome 5 (2017)

Voir la notice de l'article provenant de la source Cambridge University Press

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!/\text{poly}(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. 
@article{10_1017_fms_2017_24,
     author = {DAVID ELLIS and YUVAL FILMUS and EHUD FRIEDGUT},
     title = {LOW-DEGREE {BOOLEAN} {FUNCTIONS} {ON} $S_{n}$ , {WITH} {AN} {APPLICATION} {TO} {ISOPERIMETRY}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {5},
     year = {2017},
     doi = {10.1017/fms.2017.24},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2017.24/}
}
TY  - JOUR
AU  - DAVID ELLIS
AU  - YUVAL FILMUS
AU  - EHUD FRIEDGUT
TI  - LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY
JO  - Forum of Mathematics, Sigma
PY  - 2017
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2017.24/
DO  - 10.1017/fms.2017.24
LA  - en
ID  - 10_1017_fms_2017_24
ER  - 
%0 Journal Article
%A DAVID ELLIS
%A YUVAL FILMUS
%A EHUD FRIEDGUT
%T LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY
%J Forum of Mathematics, Sigma
%D 2017
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2017.24/
%R 10.1017/fms.2017.24
%G en
%F 10_1017_fms_2017_24
DAVID ELLIS; YUVAL FILMUS; EHUD FRIEDGUT. LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY. Forum of Mathematics, Sigma, Tome 5 (2017). doi: 10.1017/fms.2017.24

Cité par Sources :