We show that the natural directed analogues of the KKL theorem and the Eldan– Gross inequality from the analysis of Boolean functions fail to hold. This is in contrast to several other isoperimetric inequalities on the Boolean hypercube (such as the Poincare inequality, Margulis’s inequality and Talagrand’s inequalit) for which directed strengthenings have recently been established.
@article{10_37236_11828,
author = {Quentin Dubroff and Shivam Nadimpalli and Bhargav Narayanan},
title = {A counterexample to {directed-KKL}},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {4},
doi = {10.37236/11828},
zbl = {1566.05140},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11828/}
}
TY - JOUR
AU - Quentin Dubroff
AU - Shivam Nadimpalli
AU - Bhargav Narayanan
TI - A counterexample to directed-KKL
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/11828/
DO - 10.37236/11828
ID - 10_37236_11828
ER -
%0 Journal Article
%A Quentin Dubroff
%A Shivam Nadimpalli
%A Bhargav Narayanan
%T A counterexample to directed-KKL
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11828/
%R 10.37236/11828
%F 10_37236_11828
Quentin Dubroff; Shivam Nadimpalli; Bhargav Narayanan. A counterexample to directed-KKL. The electronic journal of combinatorics, Tome 31 (2024) no. 4. doi: 10.37236/11828
