Sharpness of KKL on Schreier graphs

Ryan O'Donnell (Carnegie Mellon University)
Karl Wimmer (Duquesne University)


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].$$

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-12

Publication Date: March 2, 2013

DOI: 10.1214/ECP.v18-1961


  • Michael Ben-Or and Nathan Linial, Collective coin flipping, Randomness and Computation (Silvio Micali and Franco Preparata, eds.), Advances in Computing Research: A research annual, vol. 5, JAI Press, 1990, pp. 91--115.
  • Bobkov, S. G.; Götze, F. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 (1999), no. 1, 1--28. MR1682772
  • Bobkov, Sergey G.; Tetali, Prasad. Modified logarithmic Sobolev inequalities in discrete settings. J. Theoret. Probab. 19 (2006), no. 2, 289--336. MR2283379
  • Bollobás, Béla; Leader, Imre. Compressions and isoperimetric inequalities. J. Combin. Theory Ser. A 56 (1991), no. 1, 47--62. MR1082842
  • Bonami, Aline. Étude des coefficients de Fourier des fonctions de $L^{p}(G)$. (French) Ann. Inst. Fourier (Grenoble) 20 1970 fasc. 2 335--402 (1971). MR0283496
  • Bourgain, Jean; Kahn, Jeff; Kalai, Gil; Katznelson, Yitzhak; Linial, Nathan. The influence of variables in product spaces. Israel J. Math. 77 (1992), no. 1-2, 55--64. MR1194785
  • Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D. On the hardness of approximating multicut and sparsest-cut. Comput. Complexity 15 (2006), no. 2, 94--114. MR2243123
  • Dario Cordero-Erausquin and Michel Ledoux, Hypercontractive measures, Talagrand's inequality, and influences, 2011.
  • Devanur, Nikhil R.; Khot, Subhash A.; Saket, Rishi; Vishnoi, Nisheeth K. Integrality gaps for sparsest cut and minimum linear arrangement problems. STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 537--546, ACM, New York, 2006. MR2277179
  • Diaconis, P.; Saloff-Coste, L. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 (1996), no. 3, 695--750. MR1410112
  • Dinur, Irit; Safra, Samuel. On the hardness of approximating minimum vertex cover. Ann. of Math. (2) 162 (2005), no. 1, 439--485. MR2178966
  • Friedgut, Ehud. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 (1998), no. 1, 27--35. MR1645642
  • Friedgut, Ehud. Sharp thresholds of graph properties, and the $k$-sat problem. With an appendix by Jean Bourgain. J. Amer. Math. Soc. 12 (1999), no. 4, 1017--1054. MR1678031
  • Friedgut, Ehud; Kalai, Gil. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993--3002. MR1371123
  • Gao, Fuqing; Quastel, Jeremy. Exponential decay of entropy in the random transposition and Bernoulli-Laplace models. Ann. Appl. Probab. 13 (2003), no. 4, 1591--1600. MR2023890
  • Goel, Sharad. Modified logarithmic Sobolev inequalities for some models of random walk. Stochastic Process. Appl. 114 (2004), no. 1, 51--79. MR2094147
  • Gross, Leonard. Logarithmic Sobolev inequalities. Amer. J. Math. 97 (1975), no. 4, 1061--1083. MR0420249
  • Jeff Kahn, Gil Kalai, and Nathan Linial, The influence of variables on Boolean functions, Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 68--80.
  • Kamp, Jesse; Zuckerman, David. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput. 36 (2006/07), no. 5, 1231--1247. MR2284079
  • Khot, Subhash; Regev, Oded. Vertex cover might be hard to approximate to within $2-\epsilon$. J. Comput. System Sci. 74 (2008), no. 3, 335--349. MR2384079
  • Mark Krasnosel'skii and Yakov Rutickii, Convex functions and Orlicz spaces, P. Noordhoff Ltd., Groningen, 1961.
  • Krauthgamer, Robert; Rabani, Yuval. Improved lower bounds for embeddings into $L_ 1$. SIAM J. Comput. 38 (2009), no. 6, 2487--2498. MR2506299
  • Lee, Tzong-Yow; Yau, Horng-Tzer. Logarithmic Sobolev inequality for some models of random walks. Ann. Probab. 26 (1998), no. 4, 1855--1873. MR1675008
  • O'Donnell, Ryan; Servedio, Rocco A. The Chow parameters problem [extended abstract]. STOC'08, 517--526, ACM, New York, 2008. MR2582685
  • O'Donnell, Ryan; Wimmer, Karl. KKL, Kruskal-Katona, and monotone nets. 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 725--734, IEEE Computer Soc., Los Alamitos, CA, 2009. MR2648448
  • Rao, M. M.; Ren, Z. D. Theory of Orlicz spaces. Monographs and Textbooks in Pure and Applied Mathematics, 146. Marcel Dekker, Inc., New York, 1991. xii+449 pp. ISBN: 0-8247-8478-2 MR1113700
  • Ran Raz, A parallel repetition theorem, Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 1995, pp. 447--456.
  • Sushant Sachdeva and Madhur Tulsiani, Cuts in cartesian products of graphs, 2011.
  • Talagrand, Michel. On Russo's approximate zero-one law. Ann. Probab. 22 (1994), no. 3, 1576--1587. MR1303654
  • Wu, Liming. A new modified logarithmic Sobolev inequality for Poisson point processes and several applications. Probab. Theory Related Fields 118 (2000), no. 3, 427--438. MR1800540

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.