Chvátal's conjecture and correlation inequalities

Ehud Friedgut, Jeff Kahn, Gil Kalai, Nathan Keller

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)22-43
Number of pages22
JournalJournal of Combinatorial Theory. Series A
StatePublished - May 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Chvátal's conjecture
  • Correlation inequalities
  • Discrete Fourier analysis
  • Extremal combinatorics
  • Influences


Dive into the research topics of 'Chvátal's conjecture and correlation inequalities'. Together they form a unique fingerprint.

Cite this