Proof of the Kalai-Meshulam conjecture

Author: 

Chudnovsky, M
Scott, A
Seymour, P
Spirkl, S

Publication Date: 

7 July 2020

Journal: 

Israel Journal of Mathematics

Last Updated: 

2020-10-23T18:56:00.363+01:00

DOI: 

10.1007/s11856-020-2034-8

abstract: 

<p>Let&nbsp;<em>G</em>&nbsp;be a graph, and let&nbsp;<em>f</em><sub><em>G</em></sub>&nbsp;be the sum of (&minus;1)<sup>∣<em>A</em>∣</sup>, over all stable sets&nbsp;<em>A.</em>&nbsp;If&nbsp;<em>G</em>&nbsp;is a cycle with length divisible by three, then&nbsp;<em>f</em><sub><em>G</em></sub>&nbsp;= &plusmn;2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph&nbsp;<em>G</em>&nbsp;has length divisible by three, then ∣<em>f</em><sub><em>G</em></sub>∣ &le; 1. We prove this conjecture.</p>

Symplectic id: 

1070385

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article