Sharpness of KKL on Schreier graphs

DOI

10.1214/ECP.v18-1961

Document Type

Journal Article

Publication Date

3-19-2013

Publication Title

Electronic Communications in Probability

Volume

18

Keywords

Boolean functions, Cayley graphs, KKL, Log-sobolev constant, Orlicz norms, Schreier graphs

Abstract

Recently, the Kahn-Kalai-Linial (KKL) Theorem on influences of functions on {0; 1}n was extended to the setting of functions on Schreier graphs. Specifically, it was shown that for an undirected Schreier graph Sch(G,X,U) with log-Sobolev constant ρ and generating set U closed under conjugation, if f: X → {0; 1} then ε[f] g~ log(1/M[f]) · ρ · Var[f]. Here ε[f] denotes the average of f's influences, and M[f] denotes their maximum. In this work we investigate the extent to which this result is sharp. Our main result is that Talagrand's strengthened version of KKL also holds in the Schreier graph setting: We also give both positive and negative results regarding the strength of this theorem. We show: The condition that U is closed under conjugation cannot in general be eliminated. The log-Sobolev constant cannot be replaced by the modified log-Sobolev constant. The result cannot be improved for the Cayley graph on Sn with transpositions. The result can be improved for the Cayley graph on ℤnm with standard generators.

Open Access

Gold

Link to Full Text

Share

COinS