占有率、分数着色和三角形分数。
Occupancy fraction, fractional colouring, and triangle fraction.
作者信息
Davies Ewan, de Joannis de Verclos Rémi, Kang Ross J, Pirot François
机构信息
Korteweg-De Vries Institute for Mathematics University of Amsterdam Netherlands.
Department of Mathematics Radboud University Nijmegen Netherlands.
出版信息
J Graph Theory. 2021 Jul;97(4):557-568. doi: 10.1002/jgt.22671. Epub 2021 Mar 9.
Given , there exists such that, if , then for any graph on vertices of maximum degree in which the neighbourhood of every vertex in spans at most edges, (i)an independent set of drawn uniformly at random has at least vertices in expectation, and(ii)the fractional chromatic number of is at most . 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.
给定 ，存在 使得，如果 ，那么对于任何具有 个顶点且最大度为 的图 ，其中 中每个顶点的邻域至多跨越 条边，(i) 从 中均匀随机抽取的一个独立集期望上至少有 个顶点，并且 (ii) 的分数色数至多为 。一般来说，这些界在渐近意义下不能被改进超过 2 倍。人们可以将这些看作是 Ajtai、Komlós 和 Szemerédi 以及 Shearer 结果的更强版本。证明使用了对硬核模型的严格分析。
Zotero 插件