✦ LIBER ✦
A Correlation Inequality Involving Stable Set and Chromatic Polynomials
✍ Scribed by G.E. Farr
- Publisher
- Elsevier Science
- Year
- 1993
- Tongue
- English
- Weight
- 230 KB
- Volume
- 58
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
Suppose each vertex of a graph (G) is chosen with probability (p), these choices being independent. Let (A(G, p)) be the probability that no two chosen vertices are adjacent. This is essentially the clique polynomial of the complement of (G) which has been extensively studied in a variety of incarnations. We use the AhlswedeDaykin Theorem to prove that, for all (G), and all positive integers (\lambda, P(G, i) / \lambda^{n} \leqslant) (A\left(G, i{ }^{t}\right)^{\lambda}), where (P(C, i)) is the chromatic polynomial of (G). 1993 Academic Press. Inc.