On lattices with Möbius function \(\pm 1,0\). (English) Zbl 0611.06007
This paper provides simple arguments of a geometric nature to explain why the Möbius functions of certain lattices take only the values -1, 0, 1. The lattices considered are all of the form
\[
L_ 1(K)=\{\cup_{X\in M}X: M\subseteq K\}\quad or\quad L_ 2(K)=\{\emptyset \}\cup \{X: \exists Y\in K,\quad Y\subseteq X\},
\]
where K is a collection of nonempty subsets of a finite set A. Results include a theorem of C. Greene on intervals from \(\{\) 1,...,n\(\}\) and theorems related to network reliability. The proofs exhibit connections with convex polytopes and the algorithmic notion of evasiveness.
MSC:
| 06B05 | Structure theory of lattices |
| 52C07 | Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry) |
| 05A19 | Combinatorial identities, bijective combinatorics |
References:
| [1] | M. Aigner,Combinatorial Theory, Springer-Verlag, New York, 1979. · Zbl 0415.05001 · doi:10.1007/978-1-4615-6666-3 |
| [2] | M. R. Best, P. van Emde Boas, and H. W. Lenstra, Jr., A sharpened version of the Aanderaa-Rosenberg conjecture,Math. Centrum, Amsterdam, 1974. · Zbl 0294.05125 |
| [3] | B. Bollobas,Extremal Graph Theory, Academic Press, London, 1978. · Zbl 0419.05031 |
| [4] | R. Cordovil, A combinatorial perspective on the non-Radon partitions,J. Combin. Theory Ser. A38 (1985), 38-47. · Zbl 0571.05014 · doi:10.1016/0097-3165(85)90019-6 |
| [5] | P. H. Edelman, The acyclic sets of an oriented matroid,J. Combin. Theory Ser. B36 (1984), 26-31. · Zbl 0542.05023 · doi:10.1016/0095-8956(84)90011-X |
| [6] | C. Greene, A class of lattices with Mobius function ±1, 0, preprint. · Zbl 0665.06007 |
| [7] | J. Hagstrom, Combinatorial properties for directed network reliability with a path length criterion, preprint. |
| [8] | J. Kahn, M. Saks, and D. Sturtevant, A topological approach to evasiveness,Combinatorica4 (1984), 297-306. · Zbl 0577.05061 · doi:10.1007/BF02579140 |
| [9] | J. Kahn and D. Sturtevant, Reliability and Möbius functions, preprint. |
| [10] | M. Las Vergnas, Convexity in oriented matroids,J. Combin. Theory. Ser. B29 (1980), 231-243. · Zbl 0443.05026 · doi:10.1016/0095-8956(80)90082-9 |
| [11] | E. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976. · Zbl 0413.90040 |
| [12] | R. L. Rivest and J. Vuillemin, On recognizing graph properties from adjacency matrices,Theoret. Comput. Sci.3 (1976), 371-384. · Zbl 0358.68079 · doi:10.1016/0304-3975(76)90053-0 |
| [13] | G.-C. Rota, On the foundations of combinatorial theory I: theory of Möbius functions,Z. Wahrsch. Verw. Gebiete2 (1964), 340-368. · Zbl 0121.02406 · doi:10.1007/BF00531932 |
| [14] | Rota, G.-C.; Mirsky, L. (ed.), On the combinatorics of the Euler characteristic, 221-233 (1971), London · Zbl 0299.06006 |
| [15] | A. Satyanarayana, A unified formula for analysis of some network reliability problems,IEEE Trans. Reliability31 (1982), 23-32. · Zbl 0481.90032 · doi:10.1109/TR.1982.5221215 |
| [16] | A. Satyranarayana and J. Hagstrom, Combinatorial properties of directed graphs useful in computing network reliability,Networks11 (1981), 357-366. · Zbl 0468.94016 · doi:10.1002/net.3230110405 |
| [17] | A. Satyanarayana and A. Prabhakar, A new topological formula and rapid algorithm for reliability analysis of complex networks,IEEE Trans. Reliability27 (1978), 82-100. · Zbl 0409.90039 · doi:10.1109/TR.1978.5220266 |
| [18] | R. Willie, A theorem concerning cyclic directed graphs with applications to network reliability,Networks10 (1980), 71-78. · Zbl 0434.90045 · doi:10.1002/net.3230100107 |
| [19] | R. Cordovil, M. Las Vergnas, and A. Mandel, Euler’s relation, Möbius functions and matroid identities,Geom. Dedicata12 (1982), 147-162. · Zbl 0476.52010 · doi:10.1007/BF00147634 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
