Juntas in the ℓ1‐grid and Lipschitz maps between discrete tori |
| |
| Authors: | Itai Benjamini David Ellis Ehud Friedgut Nathan Keller Arnab Sen |
| |
| Affiliation: | 1. Department of Mathematics, Weizmann Institute of Science, Rehovot, Israel;2. School of Mathematical Sciences, Queen Mary, University of London, London, UK;3. Department of Mathematics, Bar Ilan University, Ramat Gan, Israel;4. School of Mathematics, University of Minnesota, Minneapolis, MN, USA |
| |
| Abstract: | We show that if  , then  is  ‐close to a junta depending upon at most  coordinates, where  denotes the edge‐boundary of  in the  ‐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  ‐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 |
| |
| Keywords: | Boolean functions influence Lipschitz |
|
|
