Cargando…

Occupancy fraction, fractional colouring, and triangle fraction

Given [Formula: see text] , there exists [Formula: see text] such that, if [Formula: see text] , then for any graph [Formula: see text] on [Formula: see text] vertices of maximum degree [Formula: see text] in which the neighbourhood of every vertex in [Formula: see text] spans at most [Formula: see...

Descripción completa

Detalles Bibliográficos
Autores principales: Davies, Ewan, de Joannis de Verclos, Rémi, Kang, Ross J., Pirot, François
Formato: Online Artículo Texto
Lenguaje:English
Publicado: John Wiley and Sons Inc. 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8252119/
https://www.ncbi.nlm.nih.gov/pubmed/34248256
http://dx.doi.org/10.1002/jgt.22671
Descripción
Sumario:Given [Formula: see text] , there exists [Formula: see text] such that, if [Formula: see text] , then for any graph [Formula: see text] on [Formula: see text] vertices of maximum degree [Formula: see text] in which the neighbourhood of every vertex in [Formula: see text] spans at most [Formula: see text] edges, (i).. an independent set of [Formula: see text] drawn uniformly at random has at least [Formula: see text] vertices in expectation, and (ii).. the fractional chromatic number of [Formula: see text] is at most [Formula: see text]. 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ós and Szemerédi and Shearer. The proofs use a tight analysis of the hard‐core model.