Proof of the Kalai-Meshulam conjecture
<p>Let <em>G</em> be a graph, and let <em>f</em><sub><em>G</em></sub> be the sum of (−1)<sup>∣<em>A</em>∣</sup>, over all stable sets <em>A.</em> ...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2020
|
| _version_ | 1826305427198967808 |
|---|---|
| author | Chudnovsky, M Scott, A Seymour, P Spirkl, S |
| author_facet | Chudnovsky, M Scott, A Seymour, P Spirkl, S |
| author_sort | Chudnovsky, M |
| collection | OXFORD |
| description | <p>Let <em>G</em> be a graph, and let <em>f</em><sub><em>G</em></sub> be the sum of (−1)<sup>∣<em>A</em>∣</sup>, over all stable sets <em>A.</em> If <em>G</em> is a cycle with length divisible by three, then <em>f</em><sub><em>G</em></sub> = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph <em>G</em> has length divisible by three, then ∣<em>f</em><sub><em>G</em></sub>∣ ≤ 1. We prove this conjecture.</p> |
| first_indexed | 2024-03-07T06:32:43Z |
| format | Journal article |
| id | oxford-uuid:f68f6941-dcc6-4b37-975d-d218c5aa34af |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:32:43Z |
| publishDate | 2020 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:f68f6941-dcc6-4b37-975d-d218c5aa34af2022-03-27T12:35:58ZProof of the Kalai-Meshulam conjectureJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f68f6941-dcc6-4b37-975d-d218c5aa34afEnglishSymplectic Elements at OxfordSpringer2020Chudnovsky, MScott, ASeymour, PSpirkl, S<p>Let <em>G</em> be a graph, and let <em>f</em><sub><em>G</em></sub> be the sum of (−1)<sup>∣<em>A</em>∣</sup>, over all stable sets <em>A.</em> If <em>G</em> is a cycle with length divisible by three, then <em>f</em><sub><em>G</em></sub> = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the conjecture that, if no induced cycle of a graph <em>G</em> has length divisible by three, then ∣<em>f</em><sub><em>G</em></sub>∣ ≤ 1. We prove this conjecture.</p> |
| spellingShingle | Chudnovsky, M Scott, A Seymour, P Spirkl, S Proof of the Kalai-Meshulam conjecture |
| title | Proof of the Kalai-Meshulam conjecture |
| title_full | Proof of the Kalai-Meshulam conjecture |
| title_fullStr | Proof of the Kalai-Meshulam conjecture |
| title_full_unstemmed | Proof of the Kalai-Meshulam conjecture |
| title_short | Proof of the Kalai-Meshulam conjecture |
| title_sort | proof of the kalai meshulam conjecture |
| work_keys_str_mv | AT chudnovskym proofofthekalaimeshulamconjecture AT scotta proofofthekalaimeshulamconjecture AT seymourp proofofthekalaimeshulamconjecture AT spirkls proofofthekalaimeshulamconjecture |