Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-24T02:39:11.807Z Has data issue: false hasContentIssue false

The Kruskal-Katona Theorem and a Characterization of System Signatures

Published online by Cambridge University Press:  30 January 2018

Alessandro D'Andrea*
Affiliation:
Università degli Studi di Roma ‘La Sapienza’
Luca De Sanctis*
Affiliation:
Università degli Studi di Roma ‘La Sapienza’
*
Postal address: Dipartimento di Matematica, Università degli Studi di Roma ‘La Sapienza’, Piazzale Aldo Moro 5, Rome, 00185, Italy.
∗∗ Postal address: Dipartimento di Matematica, Università degli Studi di Roma ‘La Sapienza’, Piazzale Aldo Moro 5, Rome, 00185, Italy. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show how to determine if a given vector can be the signature of a system on a finite number of components and, if so, exhibit such a system in terms of its structure function. The method employs combinatorial results from the theory of (finite) simplicial complexes, and provides a full characterization of signature vectors using a theorem of Kruskal (1963) and Katona (1968). We also show how the same approach can provide new combinatorial proofs of further results, e.g. that the signature vector of a system cannot have isolated zeroes. Finally, we prove that a signature with all nonzero entries must be a uniform distribution.

Type
Research Article
Copyright
© Applied Probability Trust 

References

Boland, P. J. (2001). Signatures of indirect majority systems. J. Appl. Prob. 38, 597603.Google Scholar
Gertsbakh, I. (2000). Reliability Theory. With Applications to Preventive Maintenance. Springer, Berlin.Google Scholar
Katona, G. (1968). A theorem of finite sets. In Theory of Graphs, Academic Press, New York, pp. 187207.Google Scholar
Kruskal, J. B. (1963). The number of simplices in a complex, In Mathematical Optimization Techniques, University of California Press, Berkeley, pp. 251278.Google Scholar
Navarro, J. and Rubio, R. (2010). Computations of signatures of coherent systems with five components. Comm. Statist. Simul. Comput. 39, 6884.Google Scholar
Ross, S. M., Shahshahani, M. and Weiss, G. (1980). On the number of component failures in systems whose component lives are exchangeable. Math. Operat. Res. 5, 358365.Google Scholar
Samaniego, F. J. (2007). System Signatures and Their Applications in Engineering Reliability, (Internat. Ser. Operat. Res. Manag. Sci. 110). Springer, New York.Google Scholar