Juntas in the ℓ1‐grid and Lipschitz maps between discrete tori1. Issue 2 (14th November 2015)

• Record Type: Journal Article
• Authors: Benjamini, Itai; Ellis, David; Friedgut, Ehud; Keller, Nathan; Sen, Arnab
• Is Part Of: Random structures & algorithms. Volume 49:Issue 2(2016)
• Page Start: 253
• Page End: 279
• Publication Date: 2015-11-14
• Subjects: Boolean functions -- influence -- Lipschitz; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20623
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We show that if A ⊂ [ k ] n, then A is ϵ ‐close to a junta depending upon at most exp ( O ( | ∂ A | / ( k n − 1 ϵ ) ) ) coordinates, where ∂ A denotes the edge‐boundary of A in the ℓ 1 ‐grid. This bound is sharp up to the value of the absolute constant in the exponent. This result can be seen as a generalisation of the Junta theorem for the discrete cube, from [6], or as a characterisation of large subsets of the ℓ 1 ‐grid whose edge‐boundary is small. We use it to prove a result on the structure of Lipschitz functions between two discrete tori; this can be seen as a discrete, quantitative analogue of a recent result of Austin [1]. We also prove a refined version of our junta theorem, which is sharp in a wider range of cases. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 253–279, 2016