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
_version_ 1783717235130368000
author Davies, Ewan
de Joannis de Verclos, Rémi
Kang, Ross J.
Pirot, François
author_facet Davies, Ewan
de Joannis de Verclos, Rémi
Kang, Ross J.
Pirot, François
author_sort Davies, Ewan
collection PubMed
description 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.
format Online
Article
Text
id pubmed-8252119
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher John Wiley and Sons Inc.
record_format MEDLINE/PubMed
spelling pubmed-82521192021-07-07 Occupancy fraction, fractional colouring, and triangle fraction Davies, Ewan de Joannis de Verclos, Rémi Kang, Ross J. Pirot, François J Graph Theory Articles 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. John Wiley and Sons Inc. 2021-03-09 2021-07 /pmc/articles/PMC8252119/ /pubmed/34248256 http://dx.doi.org/10.1002/jgt.22671 Text en © 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC https://creativecommons.org/licenses/by/4.0/This is an open access article under the terms of the http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
spellingShingle Articles
Davies, Ewan
de Joannis de Verclos, Rémi
Kang, Ross J.
Pirot, François
Occupancy fraction, fractional colouring, and triangle fraction
title Occupancy fraction, fractional colouring, and triangle fraction
title_full Occupancy fraction, fractional colouring, and triangle fraction
title_fullStr Occupancy fraction, fractional colouring, and triangle fraction
title_full_unstemmed Occupancy fraction, fractional colouring, and triangle fraction
title_short Occupancy fraction, fractional colouring, and triangle fraction
title_sort occupancy fraction, fractional colouring, and triangle fraction
topic Articles
url 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
work_keys_str_mv AT daviesewan occupancyfractionfractionalcolouringandtrianglefraction
AT dejoannisdeverclosremi occupancyfractionfractionalcolouringandtrianglefraction
AT kangrossj occupancyfractionfractionalcolouringandtrianglefraction
AT pirotfrancois occupancyfractionfractionalcolouringandtrianglefraction