Proof of the Kalai-Meshulam conjecture
- PDF / 289,628 Bytes
- 23 Pages / 429.408 x 636.768 pts Page_size
- 19 Downloads / 183 Views
PROOF OF THE KALAI–MESHULAM CONJECTURE
BY
Maria Chudnovsky∗ Department of Mathematics, Fine Hall, Washington Road, Princeton University, Princeton, NJ 08544, USA e-mail: [email protected] AND
Alex Scott∗∗ Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK e-mail: [email protected] AND
Paul Seymour† and Sophie Spirkl Department of Mathematics, Fine Hall, Washington Road, Princeton University, Princeton, NJ 08544, USA e-mail: [email protected], [email protected]
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.
∗ Supported by NSF Grant DMS-1763817. This material is based upon work sup-
ported 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. Received July 17, 2018 and in revised form April 29, 2019
1
2
M. CHUDNOVSKY ET AL.
Isr. J. Math.
1. Introduction In the late 1990’s, G. Kalai and R. Meshulam [8] made an intriguing sequence of conjectures about the connections between induced cycle lengths, chromatic number, and the number of stable sets of different parities in a graph. A graph is ternary if no induced cycle has length a multiple of three; thus, ternary graphs have no triangles. (All graphs in this paper are finite and have no loops or parallel edges.) First, Kalai and Meshulam conjectured: 1.1: There exists c such that every ternary graph is c-colourable. This was proved by Bonamy, Charbit and Thomass´e [1], for some large constant c (although it may be that all ternary graphs are 3-colourable, and this remains open). A much stronger result was later proved by two of us [9]: that for all integers p, q ≥ 0, every graph with bounded clique number and with no induced cycle of length p modulo q has bounded chromatic number. Second, Kalai and Meshulam conjectured: 1.2: For every ternary graph, the number of stable sets with even cardinality and the number with odd cardinality differ by at most one. This has remained open, and we prove it in this paper. Two further conjectures of Kalai and Meshulam were proved in [9]. The stronger of these conjectures stated that for all k there exists c, such that, if for every induced subgraph of G the number of even stable sets and the number of odd ones differ by at most k, then G is c-colourable. This follows from a generalization of the strengthening of 1.1 mentioned above. A final Kalai–Meshulam conjecture concerns Betti numbers and ternary graphs. The independence complex I(G) of a graph G is the simplicial complex whose faces are the stable sets of vertices of G. Let bi denote the ith Betti number of I(G) and let b(G) denote the sum of the Betti nu
Data Loading...
