A correlation inequality involving stable set and chromatic polynomials (Q810040): Difference between revisions

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 and has been extensively studied in a variety of incarnations. Let P(G,\(\lambda\)) be the chromatic polynomial of G. We use the Ahlswede-Daykin Theorem to prove that, for all G and all positive integers \(\lambda\), \(P(G,\lambda)/\lambda^ n\leq A(G,\lambda^{- 1})^{\lambda}\).