TY - JOUR
T1 - Proof of the Kalai-Meshulam conjecture
AU - Chudnovsky, Maria
AU - Scott, Alex
AU - Seymour, Paul
AU - Spirkl, Sophie
N1 - Funding Information:
Supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563.
Funding Information:
Supported by a Leverhulme Trust Research Fellowship.
Funding Information:
Supported by NSF Grant DMS-1763817. This material is based upon work supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under grant number W911NF-16-1-0404.
Publisher Copyright:
© 2020, The Hebrew University of Jerusalem.
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 - http://www.scopus.com/inward/record.url?scp=85087609961&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087609961&partnerID=8YFLogxK
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 -