Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Influential Coalitions for Boolean Functions I: Constructions
Received: February 16, 2013
Revised: October 12, 2020
Published: September 30, 2024
Download article from ToC site:
[PDF (300K)] [PS (1090K)] [Source ZIP]
Keywords: Boolean functions, influence, trace of set-systems, discrete isoperimetric inequalities, tribes
ACM Classification: G.2.1, G.2.m
AMS Classification: 05D05, 68R05, 60C05

Abstract: [Plain Text Version]

\newcommand{\ga}[0]{\alpha } \newcommand{\gd}[0]{\delta }

For f:\{0,1\}^n \to \{0,1\} and S\subset \{1,2,\dots,n\}, let J^+_S(f) be the probability that, for x uniform from \{0,1\}^n, there is some y\in \{0,1\}^n with f(y)=1 and x\equiv y outside S. We are interested in estimating, for given \mu (f) (:= \mathbb E(f)) and m, the least possible value of \max\{J^+_S(f): |S|=m\}.

A theorem of Kahn, Kalai, and Linial (KKL) gave some understanding of this issue and led to several stronger conjectures. Here we disprove a pair of conjectures from the late 80s, as follows.

(1) The KKL Theorem implies that there is a fixed \alpha> 0 so that if \mu (f)\approx 1/2, and c> 0, then there is a set S of size at most \alpha cn with J^+_S(f) \ge 1-n^{-c}. We show that for every \delta > 0 there is an f with \mu (f)\approx 1/2 and J^+_S(f) \le 1-n^{-C} for every S of size (1/2-\delta) n, where C=C_\delta. This disproves a conjecture of Benny Chor from 1989.

(2) We also show that for fixed \gd> 0 there are c,\ga > 0 and Boolean functions f such that \mu (f) > \exp[-n^{1-c}] and J^+_S(f) \le \exp[-n^\ga] for each S of size (1/2-\gd)n. This disproves a conjecture of the third author from the late 80s.