Chvátal's Conjecture and Correlation Inequalities

2016/08/31 by Friedgut, Ehud, Kahn, Jeff, Kalai, Gil +1 · 1 citation
#05D05 #05D40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.08954

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.

Cited by

• Talagrand-Type Correlation Inequalities for Supermodular and Submodular Functions on the Hypercube

Related

• Chvátal's conjecture for downsets of small rank
• Kleitman's conjecture for central families
• Two extremal problems on intersecting families
• The Hajnal--Rothschild problem
• Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New