Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903763 | Journal of Combinatorial Theory, Series A | 2018 | 22 Pages |
Abstract
Chvátal's conjecture in extremal combinatorics asserts that for any decreasing family F of subsets of a finite set S, there is a largest intersecting subfamily of F consisting of all members of F that include a particular xâS. In this paper we reformulate the conjecture in terms of influences of variables on Boolean functions and correlation inequalities, and study special cases and variants using tools from discrete Fourier analysis.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ehud Friedgut, Jeff Kahn, Gil Kalai, Nathan Keller,