A correlation inequality involving stable set and chromatic polynomials (Q810040): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Normalize DOI. |
||
(One intermediate revision by one other user not shown) | |||
Property / DOI | |||
Property / DOI: 10.1006/jctb.1993.1026 / rank | |||
Property / DOI | |||
Property / DOI: 10.1006/JCTB.1993.1026 / rank | |||
Normal rank |
Latest revision as of 03:42, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A correlation inequality involving stable set and chromatic polynomials |
scientific article |
Statements
A correlation inequality involving stable set and chromatic polynomials (English)
0 references
1993
0 references
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}\).
0 references
correlation inequality
0 references
graph polynomial
0 references
clique polynomial
0 references
chromatic polynomial
0 references
Ahlswede-Daykin Theorem
0 references