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

CREATORAnders Martinsson, Raphael Steiner
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00567

Browse the full library · About the Tower of Babel