FKN theorem for the multislice, with applications. (English) Zbl 1469.94251
Summary: The Friedgut-Kalai-Naor (FKN) theorem states that if \(f\) is a Boolean function on the Boolean cube which is close to degree one, then \(f\) is close to a dictator, a function depending on a single coordinate. The author has extended the theorem to the slice, the subset of the Boolean cube consisting of all vectors with fixed Hamming weight. We extend the theorem further, to the multislice, a multicoloured version of the slice. As an application, we prove a stability version of the edge-isoperimetric inequality for settings of parameters in which the optimal set is a dictator.
MSC:
| 94D10 | Boolean functions |
| 06E30 | Boolean functions |
| 60C05 | Combinatorial probability |
| 60E15 | Inequalities; stochastic orderings |
Keywords:
Friedgut-Kalai-Naor theoremReferences:
| [1] | Alon, N., Dinur, I., Friedgut, E. and Sudakov, B. (2004) Graph products, Fourier analysis and spectral techniques. Geom. Funct. Anal. 14913-940. · Zbl 1056.05104 |
| [2] | Diaconis, P. and Shahshahani, M. (1981) Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete57159-179. · Zbl 0485.60006 |
| [3] | Dikstein, Y., Dinur, I., Filmus, Y. and Harsha, P. (2018) Boolean function analysis on high-dimensional expanders. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM 2018), Vol. 116 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, pp. 38:1-38:20. · Zbl 1522.68739 |
| [4] | Ellis, D., Filmus, Y. and Friedgut, E. (2015) A quasi-stability result for dictatorships in S_n. Combinatorica35573-618. · Zbl 1389.05167 |
| [5] | Ellis, D., Filmus, Y. and Friedgut, E. (2015) A stability result for balanced dictatorships in S_n. Random Struct. Alg . 46494-530. · Zbl 1342.94135 |
| [6] | Ellis, D., Friedgut, E. and Pilpel, H. (2011) Intersecting families of permutations. J. Amer. Math. Soc. 24649-682. · Zbl 1285.05171 |
| [7] | Filmus, Y. (2016) Friedgut-Kalai-Naor theorem for slices of the Boolean cube. Chic. J. Theoret. Comput. Sci. 2016 14:1-14:17. · Zbl 1401.06014 |
| [8] | Filmus, Y. and Ihringer, F. (2019) Boolean degree 1 functions on some classical association schemes. J. Combin. Theory Ser. A162241-270. · Zbl 1401.05317 |
| [9] | Filmus, Y., O’Donnell, R. and Wu, X. (2018) A log-Sobolev inequality for the multislice, with applications. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Vol. 124 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, pp. 34:1-34:12. · Zbl 07559077 |
| [10] | Friedgut, E., Kalai, G. and Naor, A. (2002) Boolean functions whose Fourier transform is concentrated on the first two levels and neutral social choice. Adv. Appl. Math. 29427-437. · Zbl 1039.91014 |
| [11] | Frobenius, G. (1900) Über die Charaktere der symmetrischen Gruppe. Sitzungsberichte der Königlich preussischen Akademie der Wissenschaften zu Berlin, pp. 516-534. · JFM 31.0129.02 |
| [12] | Jendrej, J., Oleszkiewicz, K. and Wojtaszczyk, J. O. (2015) On some extensions of the FKN theorem. Theory Comput. 11445-469. · Zbl 1352.60029 |
| [13] | Nayar, P. (2014) FKN theorem on the biased cube. Colloq. Math. 137253-261. · Zbl 1309.42040 |
| [14] | O’Donnell, R. (2014) Analysis of Boolean Functions, Cambridge University Press. · Zbl 1336.94096 |
| [15] | Rubinstein, A. (2012) Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input. Master’s thesis, Tel Aviv University, Israel. |
| [16] | Sagan, B. E. (2001) The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, second edition, Vol. 203 of Graduate Texts in Mathematics, Springer. · Zbl 0964.05070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
