Occupancy fraction, fractional colouring, and triangle fraction
Copyright policy )Occupancy fraction, fractional colouring, and triangle fraction
Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le ��^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $��$ in which the neighbourhood of every vertex in $G$ spans at most $��^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/��)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\varepsilon)��/\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��s and Szemer��di (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model.
13 pages
- Radboud University Nijmegen Netherlands
- University of Lorraine France
- Universiteit van Amsterdam, Faculteit der Natuurwetenschappen, Wiskunde en Informatica (Faculty of Science), Korteweg-de Vries Instituut voor de Wiskunde
- French Institute for Research in Computer Science and Automation France
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek Netherlands
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Probability (math.PR), Articles, hard-core model, fractional colouring, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], 05C35, 05D10 (Primary), 05C15 (Secondary), Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), independent sets, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), hard‐core model, Mathematics, Mathematics - Probability, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Probability (math.PR), Articles, hard-core model, fractional colouring, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], 05C35, 05D10 (Primary), 05C15 (Secondary), Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), independent sets, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), hard‐core model, Mathematics, Mathematics - Probability, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!