FKN theorem for the multislice, with applications. (18th March 2020)

• Record Type: Journal Article
• Authors: Filmus, Yuval
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 2(2020)
• Page Start: 200
• Page End: 212
• Publication Date: 2020-03-18
• Subjects: 26D07, -- 42B10, -- 94C10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548319000361
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: The Friedgut–Kalai–Naor (FKN) theorem states that if ƒ is a Boolean function on the Boolean cube which is close to degree one, then ƒ 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.