Local Shearer bound
Anders Martinsson, Raphael Steiner · 2025
Read Local Shearer bound by Anders Martinsson, Raphael Steiner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00567.txt.
Description
Anders Martinsson and Raphael Steiner prove a local strengthening of Shearer's classic bound on independent sets in triangle-free graphs. Shearer's bound caps how large a set of mutually unlinked vertices can be. Their version hands each graph a lottery over its independent sets.
In that lottery, every vertex lands in the drawn set with a chance near the classic ratio for its own degree. The result settles a main conjecture on fractional coloring with local demands from 2018. It also confirms a bound on the fractional chromatic number of triangle-free graphs. A weighted general theorem drives the proof, and a new spectral bound falls out as a bonus.
Catalog record
| CREATOR | Anders Martinsson, Raphael Steiner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00567