2014/09/10 by Jean Bourgain, Jeff Kahn, Bourgain, Jean +3
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1409.3033
21 pages. Some of the results are included in arXiv:1308.2794
arxiv created 2014/09/10 · openalex publication_date 2014/09/10 · arxiv updated 2014/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We improve results of Kahn, Kalai, and Linial from the late 80s on the existence of influential large coalitions for Boolean functions, and we give counterexamples to conjectures (of Benny Chor and others) also from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions. The large gaps between the new upper and lower bounds leave a lot of room for further study.