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

From MaRDI portal
Set OpenAlex properties.
Import241208061232 (talk | contribs)
Normalize DOI.
 
(One intermediate revision by one other user not shown)
Property / DOI
 
Property / DOI: 10.1006/jctb.1993.1026 / rank
Normal 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
    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

    Identifiers