Sharpness of KKL on Schreier graphs
@article{ECP1961,
author = {Ryan O'Donnell and Karl Wimmer},
title = {Sharpness of KKL on Schreier graphs},
journal = {Electron. Commun. Probab.},
fjournal = {Electronic Communications in Probability},
volume = {18},
year = {2013},
keywords = {boolean functions; KKL; Cayley graphs; Schreier graphs; log-sobolev constant; Orlicz norms},
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 $\text{Sch}(G,X,U)$ with log Sobolev constant $\rho$ and generating set $U$ closed under conjugation, if $f : X \to \{0,1\}$ then $$\mathcal{E}[f] \gtrsim \log(1/\text{MaxInf}[f]) \cdot \rho \cdot {\bf Var}[f].$$ Here $\mathcal{E}[f]$ denotes the average of $f$'s influences, and $\text{MaxInf}[f]$ denotes their maximum. In this work we investigate the extent to which this result is sharp. We show:
1. The condition that $U$ is closed under conjugation cannot in general be eliminated.
2. The log-Sobolev constant cannot be replaced by the modified log-Sobolev constant.
3. The result cannot be improved for the Cayley graph on $S_n$ with transpositions.
4. The result can be improved for the Cayley graph on $\mathbb{Z}_m^n$ with standard generators.
5. Talagrand's strengthened version of KKL also holds in the Schreier graph setting: $$\mathrm{avg}_{u \in U} \{\mathrm{Inf}_u[f]/\log(1/\mathrm{Inf}_u[f]) \} \gtrsim \rho \cdot {\bf Var}[f].$$
},
pages = {no. 18, 1-12},
issn = {1083-589X},
doi = {10.1214/ECP.v18-1961},
url = {http://ecp.ejpecp.org/article/view/1961}}