Sharpness of KKL on 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.