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...
Autores principales: | , , , |
---|---|
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 |