LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY
We prove that Boolean functions on $S_{n}$ , whose Fourier transform is highly concentrated on irreducible representations indexed by partitions of...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2017-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S205050941700024X/type/journal_article |
| _version_ | 1811156235472338944 |
|---|---|
| author | DAVID ELLIS YUVAL FILMUS EHUD FRIEDGUT |
| author_facet | DAVID ELLIS YUVAL FILMUS EHUD FRIEDGUT |
| author_sort | DAVID ELLIS |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T04:47:10Z |
| format | Article |
| id | doaj.art-629f3998f4b94fda8b5c53d0e32fdaac |
| institution | Directory Open Access Journal |
| issn | 2050-5094 |
| language | English |
| last_indexed | 2024-04-10T04:47:10Z |
| publishDate | 2017-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj.art-629f3998f4b94fda8b5c53d0e32fdaac2023-03-09T12:34:43ZengCambridge University PressForum of Mathematics, Sigma2050-50942017-01-01510.1017/fms.2017.24LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRYDAVID ELLIS0YUVAL FILMUS1EHUD FRIEDGUT2School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK;Computer Science Department, Technion – Israel Institute of Technology, Technion City, Haifa 3200003, Israel;Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot 76100, Israel;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.https://www.cambridge.org/core/product/identifier/S205050941700024X/type/journal_article05D05 |
| spellingShingle | DAVID ELLIS YUVAL FILMUS EHUD FRIEDGUT LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY Forum of Mathematics, Sigma 05D05 |
| title | LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY |
| title_full | LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY |
| title_fullStr | LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY |
| title_full_unstemmed | LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY |
| title_short | LOW-DEGREE BOOLEAN FUNCTIONS ON $S_{n}$ , WITH AN APPLICATION TO ISOPERIMETRY |
| title_sort | low degree boolean functions on s n with an application to isoperimetry |
| topic | 05D05 |
| url | https://www.cambridge.org/core/product/identifier/S205050941700024X/type/journal_article |
| work_keys_str_mv | AT davidellis lowdegreebooleanfunctionsonsnwithanapplicationtoisoperimetry AT yuvalfilmus lowdegreebooleanfunctionsonsnwithanapplicationtoisoperimetry AT ehudfriedgut lowdegreebooleanfunctionsonsnwithanapplicationtoisoperimetry |