Article contents
The Kruskal-Katona Theorem and a Characterization of System Signatures
Published online by Cambridge University Press: 30 January 2018
Abstract
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.
MSC classification
- Type
- Research Article
- Information
- Copyright
- © Applied Probability Trust
References
- 8
- Cited by