Combinatorial and Geometric View of the System Reliability Theory
Associated to every coherent system there is a canonical ideal whose Hilbert series encodes the reliability of the system. We study various ideals arising in the theory of system reliability. Using ideas from the theory of orientations, and matroids on gr
- PDF / 160,168 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 18 Downloads / 179 Views
Abstract. Associated to every coherent system there is a canonical ideal whose Hilbert series encodes the reliability of the system. We study various ideals arising in the theory of system reliability. Using ideas from the theory of orientations, and matroids on graphs we associate a polyhedral complex to our system so that the non-cancelling terms in the reliability formula can be read from the labeled faces of this complex. Algebraically, this polyhedron resolves the minimal free resolution of these ideals. In each case, we give an explicit combinatorial description of non-cancelling terms in terms of acyclic orientations of graph and the number of regions in the graphic hyperplane arrangement. This resolves open questions posed by Giglio-Wynn and develops new connections between the theory of oriented matroid, the theory of divisors on graphs, and the theory of system reliability.
Keywords: System reliability complex · Orientations
1
·
Betti numbers
·
Polyhedral cellular
Introduction
Inspired by the work of Naiman-Wynn [NW92] and Giglio-Wynn [GW04] connecting system reliability to Hilbert functions of their associated ideals, we study reliability of networks through the lens of polyhedral geometry. We apply the syzygy tool from commutative algebra to encode the (non-cancelling) terms in the reliability formula for various systems. This gives a more clear insight into the structure of our systems. The starting point of this paper is to study the following network flow reliability problem. Let G = (V, E) be a graph. Assume that the vertices are reliable but each edge may fail (with the probability 1 − pe ). A popular game in system reliability theory is to compute the probability of the union of certain events under various restrictions. The classical method to compute the system reliability is to apply the inclusion-exclusion principle of probability theory which is computationally expensive. On the other hand, the system reliability formula is equal to the numerator of Hilbert series of a certain ideal associated to the network. The special networks have been studied in [GW04], and the general c Springer International Publishing Switzerland 2016 G.-M. Greuel et al. (Eds.): ICMS 2016, LNCS 9725, pp. 148–153, 2016. DOI: 10.1007/978-3-319-42432-3 19
Combinatorial and Geometric View of the System Reliability Theory
149
case was stated as an open problem. We recommend [Doh03, Sect. 6] and the survey articles [AB84] by Agrawal-Barlow, and [JMM88] by Johnson-Malek for an overview of the subject.
2
Source-to-Multiple-Terminal (SMT) System
A well-known example in the theory of system reliability is the SMT system. We fix a pointed graph (G, s) with the edge set E(G), and the oriented edge set E(G). We study the probability that there exists at least one (oriented) path from s to every other vertex of G. We let R = k[x] be the polynomial ring in the variables {xe : e ∈ E(G)}. The ideal corresponding to the SMT system is the spanning tree ideal of G. For each spanning tree T of G, let OT denote the orientation
Data Loading...
