Proof of the Kalai-Meshulam conjecture

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)639-661
Number of pages23
JournalIsrael Journal of Mathematics
Volume238
Issue number2
DOIs
StatePublished - Jul 1 2020

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Proof of the Kalai-Meshulam conjecture'. Together they form a unique fingerprint.

Cite this