Cohen-Macaulay rings in network reliability

Jason I. Brown, Charles J. Colbourn, David G. Wagner

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


For any simplicial complex Δ and field K, one can associate a graded K-algebra K[Δ] (the Stanley-Reisner ring). For certain Δ and K, the Stanley-Reisner rings have a homogeneous system of parameters, Θ, such that K[Δ]/〈Θ〉 is finite-dimensional, and coefficients of its Hilbert series are the h-vector of Δ. The previous constructions of Θ were noncombinatorial. In the special case of cographic matroids, we give (for any field K) a combinatorial description of a homogeneous system of parameters in terms of the graph structure, as well as an explicit basis for the resulting quotient algebra. The results have applications to a central problem of reliability, namely the association of a multicomplex to a connected graph, such that the reliability is a simple function of the rank numbers.

Original languageEnglish (US)
Pages (from-to)377-392
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Issue number3
StatePublished - Aug 1996
Externally publishedYes


  • Cohen-Macaulay ring
  • Graph
  • Gröbner basis
  • Homogeneous system of parameters
  • Reliability

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Cohen-Macaulay rings in network reliability'. Together they form a unique fingerprint.

Cite this