Chvátal's conjecture and correlation inequalities

Ehud Friedgut; Jeff Kahn; Gil Kalai; Nathan Keller

doi:10.1016/j.jcta.2017.11.015

Chvátal's conjecture and correlation inequalities

Ehud Friedgut, Jeff Kahn, Gil Kalai, Nathan Keller

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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.

Original language	English (US)
Pages (from-to)	22-43
Number of pages	22
Journal	Journal of Combinatorial Theory. Series A
Volume	156
DOIs	https://doi.org/10.1016/j.jcta.2017.11.015
State	Published - May 2018

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

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

Access to Document

10.1016/j.jcta.2017.11.015

Cite this

@article{435d1aa3d2ca4b8082cf35dd10f4391a,

title = "Chv{\'a}tal's conjecture and correlation inequalities",

abstract = "Chv{\'a}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.",

keywords = "Chv{\'a}tal's conjecture, Correlation inequalities, Discrete Fourier analysis, Extremal combinatorics, Influences",

author = "Ehud Friedgut and Jeff Kahn and Gil Kalai and Nathan Keller",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2018",

month = may,

doi = "10.1016/j.jcta.2017.11.015",

language = "English (US)",

volume = "156",

pages = "22--43",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Chvátal's conjecture and correlation inequalities

AU - Friedgut, Ehud

AU - Kahn, Jeff

AU - Kalai, Gil

AU - Keller, Nathan

PY - 2018/5

Y1 - 2018/5

N2 - 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.

AB - 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.

KW - Chvátal's conjecture

KW - Correlation inequalities

KW - Discrete Fourier analysis

KW - Extremal combinatorics

KW - Influences

UR - http://www.scopus.com/inward/record.url?scp=85040665328&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040665328&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2017.11.015

DO - 10.1016/j.jcta.2017.11.015

M3 - Article

AN - SCOPUS:85040665328

SN - 0097-3165

VL - 156

SP - 22

EP - 43

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -

Chvátal's conjecture and correlation inequalities

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this