Occupancy fraction, fractional colouring, and triangle fraction
| Autor: | François Pirot, Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) 0102 computer and information sciences 01 natural sciences Article 05C35 05D10 (Primary) 05C15 (Secondary) Combinatorics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Fraction (mathematics) Chromatic scale 0101 mathematics Mathematics Probability (math.PR) 010102 general mathematics Neighbourhood (graph theory) Articles fractional colouring Vertex (geometry) independent sets 010201 computation theory & mathematics Independent set Graph (abstract data type) Combinatorics (math.CO) Geometry and Topology hard‐core model Mathematics - Probability Computer Science - Discrete Mathematics |
| Zdroj: | Journal of Graph Theory, 97, 4, pp. 557-568 Journal of Graph Theory, 97, 557-568 Journal of Graph Theory |
| ISSN: | 0364-9024 |
| Popis: | Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le \Delta^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $\Delta$ in which the neighbourhood of every vertex in $G$ spans at most $\Delta^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/\Delta)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\varepsilon)\Delta/\log f$. These bounds cannot in general be improved by more than a factor $2$ asymptotically. One may view these as stronger versions of results of Ajtai, Koml\'os and Szemer\'edi (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model. Comment: 13 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text