Proof of the Kalai-Meshulam conjecture

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1007/s11856-020-2034-8

Proof of the Kalai-Meshulam conjecture

Maria Chudnovsky
, Alex Scott
, Paul Seymour
, Sophie Spirkl

Mathematics

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

11 Scopus citations

Abstract

Let G be a graph, and let f_G be the sum of (−1)^∣A∣, over all stable sets A. If G is a cycle with length divisible by three, then f_G = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph G has length divisible by three, then ∣f_G∣ ≤ 1. We prove this conjecture.

Original language	English (US)
Pages (from-to)	639-661
Number of pages	23
Journal	Israel Journal of Mathematics
Volume	238
Issue number	2
DOIs	https://doi.org/10.1007/s11856-020-2034-8
State	Published - Jul 1 2020

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/s11856-020-2034-8

Cite this

@article{033d5fa70a214a3d9c54528f4ada9094,

title = "Proof of the Kalai-Meshulam conjecture",

abstract = "Let G be a graph, and let fG be the sum of (−1)∣A∣, over all stable sets A. If G is a cycle with length divisible by three, then fG = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph G has length divisible by three, then ∣fG∣ ≤ 1. We prove this conjecture.",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2020, The Hebrew University of Jerusalem.",

year = "2020",

month = jul,

day = "1",

doi = "10.1007/s11856-020-2034-8",

language = "English (US)",

volume = "238",

pages = "639--661",

journal = "Israel Journal of Mathematics",

issn = "0021-2172",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Proof of the Kalai-Meshulam conjecture

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2020/7/1

Y1 - 2020/7/1

N2 - Let G be a graph, and let fG be the sum of (−1)∣A∣, over all stable sets A. If G is a cycle with length divisible by three, then fG = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph G has length divisible by three, then ∣fG∣ ≤ 1. We prove this conjecture.

AB - Let G be a graph, and let fG be the sum of (−1)∣A∣, over all stable sets A. If G is a cycle with length divisible by three, then fG = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph G has length divisible by three, then ∣fG∣ ≤ 1. We prove this conjecture.

UR - https://www.scopus.com/pages/publications/85087609961

UR - https://www.scopus.com/pages/publications/85087609961#tab=citedBy

U2 - 10.1007/s11856-020-2034-8

DO - 10.1007/s11856-020-2034-8

M3 - Article

AN - SCOPUS:85087609961

SN - 0021-2172

VL - 238

SP - 639

EP - 661

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 2

ER -

Proof of the Kalai-Meshulam conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this