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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Bonamy, P. Charbit and S. Thomassé, Graphs with large chromatic number induce 3k-cycles, https://arxiv.org/abs/1408.2172.
M. Bousquet-Mélou, S. Linusson and E. Nevo, On the independence complex of square grids, Journal of Algebraic Combinatorics 27 (2008), 423–450.
G. Chen and A. Saito, Graphs with a cycle of length divisible by three, Journal of Combinatorial Theory, Series B 60 (1994), 277–292.
P. Fendley, K. Schoutens and H. van Eerten, Hard squares with negative activity, Journal of Physics. A 38 (2005), 315–322.
G. Gauthier, Graphs with no cycle length divisible by three, Ph. D. thesis, Princeton University, 2017.
A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002.
J. Jonsson, Hard squares with negative activity and rhombus tilings of the plane, Electronic Journal of Combinatorics 13 (2006), Article no. R67.
G. Kalai, When do a few colors suffice?, https://gilkalai.wordpress.com/2014/12/19/when-a-few-colors-suffice.
A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. X. Holes with specific residue, Combinatorica 39 (2019), 1105–1132.
A. Scott and A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics 118 (2005), 1151–1261.
Author information
Authors and Affiliations
Corresponding author
Additional 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.
Supported by a Leverhulme Trust Research Fellowship.
Supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563.
Rights and permissions
About this article
Cite this article
Chudnovsky, M., Scott, A., Seymour, P. et al. Proof of the Kalai-Meshulam conjecture. Isr. J. Math. 238, 639–661 (2020). https://doi.org/10.1007/s11856-020-2034-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-020-2034-8