Difference between revisions of "Möbius inversion"
Ulf Rehmann (talk | contribs) m (moved Möbius inversion to Moebius inversion: ascii title) |
Ulf Rehmann (talk | contribs) m (moved Moebius inversion to Möbius inversion over redirect: accented title) |
(No difference)
|
Revision as of 07:55, 26 March 2012
A method for inverting sums over partially ordered sets (or posets; cf. also Partially ordered set). The theory of Möbius inversion matured in the classic paper [a4] of G.-C. Rota and is a cornerstone of algebraic combinatorics (cf. also Combinatorics).
Let be a locally finite partially ordered set, that is, a poset in which every interval
is finite. The Möbius function
of
is the function on pairs of elements in
defined by the following conditions:
if
,
for all
, and the recursive relation
![]() |
When is finite, the function value
is the
-entry in the inverse of the incidence matrix of the partial order relation on
.
Let ,
be functions defined from
to a commutative ring
with unity. The Möbius inversion formula states:
![]() |
or, dually,
![]() |
For the Boolean algebra of all subsets of a set
,
when
. When
is thought of as a set of "properties" , the Möbius inversion formula yields the principle of inclusion-exclusion (cf. Inclusion-and-exclusion principle).
When is the distributive lattice of positive integers ordered by divisibility, the Möbius function
equals
unless
divides
and
is square-free, in which case it equals
, where
is the number of primes in the prime factorization of
. The classical or number-theoretic Möbius inversion formula states:
![]() |
For example, this yields the following formula for the Euler totient function , the number of positive integers not exceeding
that are relatively prime to
(cf. also Euler function):
![]() |
The Möbius function satisfies many identities. Four often-used identities are:
a) The P. Hall identity:
![]() |
where is the number of (strict) chains
with
links starting at
and ending at
(cf. also Chain).
b) The Weisner theorem: Let be a finite lattice with minimum
. If
and
are elements of
such that
, then
![]() |
the sum ranging over all elements such that
and
.
c) The Crapo complementation theorem: An element is a complement of an element
in a lattice
with minimum
and maximum
if
and
. For any element
in a finite lattice
,
![]() |
the sum ranging over all pairs and
such that
and both
and
are complements of
.
d) The Boolean expansion lemma: If is a closure operator on a set
(cf. also Closure space), then for a closed set
in the lattice of closed sets,
![]() |
The Boolean expansion lemma is a special case of the Galois connection theorem. It is also a special case of the cross-cut theorem. A cross-cut in a finite lattice
is a set of elements of
satisfying:
1) does not contain the minimum
or the maximum
2) no pair of elements of is comparable;
3) any maximal chain from to
has non-empty intersection with
. A subset
of elements of
is spanning if both the join of all the elements in
is
and the meet of all the elements in
is
. If
is a finite lattice with more than two elements and
is a cross-cut in
, then
![]() |
where is the number of spanning subsets of
with
elements.
Besides order-theoretic, homological and counting proofs of these results, there are also proofs using the Möbius algebra, a generalization of the Burnside algebra of a group.
Much work has been done on calculating Möbius functions of specific partially ordered sets. For example, if and
are subspaces in the lattice of subspaces of a finite-dimensional vector space over a finite field of order
and
, then
![]() |
where is the difference
.
There are many results relating structural properties and properties of the Möbius function. Two examples follow. For an element in a lattice,
only if the element
is a join of atoms. (Atoms are elements covering the minimum
; cf. also Atom.) If
is a finite lattice in which
is non-zero for all elements
, then there exists a bijection
from
to itself such that for every
,
is the maximum
.
Möbius functions occur in many proofs. For example, they are heavily used in the original proof of Dilworth's theorem that in a finite modular lattice, the number of elements covering or fewer elements equals the number of elements covered by
or fewer elements, and its extension, that the incidence matrix or combinatorial Radon transform between these two sets of elements is invertible.
The Möbius function has a homological interpretation. The value for a partially ordered set
with minimum
and maximum
is the Euler characteristic of the order complex of
, the simplicial complex whose simplices are the chains of
, the partially ordered set
with
and
deleted. Because polytopes are topologically spheres, this yields the following theorem. If
and
are faces in the face lattice of a polytope and
, then
, where
is the difference
. Taking the nerve of a covering of the order complex (cf. also Nerve of a family of sets), one obtains a homology based on a cross-cut and the cross-cut theorem.
The homological interpretation is especially interesting for a geometric lattice . In this case, the only non-trivial homology groups (cf. Homology group) are
and
, where
is the rank of
, and
is the rank or dimension of the top homology group
. Rota has proved the following sign theorem: If
is a rank-
flat in a geometric lattice, then
is positive. Indeed,
counts certain subsets in the broken-circuit complex defined by H. Whitney.
The characteristic polynomial of a ranked partially ordered set
is the polynomial
![]() |
in the variable . With simple modifications, one can obtain from the characteristic polynomial of a geometric lattice the Poincaré polynomial of an arrangement of hyperplanes and the chromatic polynomial of a graph (cf. also Graph colouring). The characteristic polynomial is an essential tool in the critical problem for matroids (cf. also Matroid). Related to the characteristic polynomial is the Eulerian function
of a finite group
, defined to be the Dirichlet polynomial
![]() |
where the sum ranges over all subgroups in the subgroup lattice of . When
is a positive integer,
is the number of
-tuples of group elements whose underlying set generate
.
The Möbius invariant of a matroid
is the integer
with
calculated in its lattice of flats if
has no loops, and
otherwise. Except when the element
is an isthmus,
satisfies the relation
![]() |
where is
with
deleted and
is
contracted at
. The triple
is an analogue of a short exact sequence (cf. also Exact sequence). Many other invariants (including the characteristic polynomial) satisfy contraction-and-deletion relations. In addition, inductive arguments involving contractions and deletions are often used in proofs.
References
[a1] | M. Barnabei, A. Brini, G.-C. Rota, "Theory of Möbius functions" Russian Math. Surveys , 3 (1986) pp. 135–188 |
[a2] | A. Björner, "Homology and shellability of matroids and geometric lattices" N.L. White (ed.) , Matroid Applications , Cambridge Univ. Press (1992) pp. 226–283 |
[a3] | J.P.S. Kung, "Radon transforms in combinatorics and lattice theory" I. Rival (ed.) , Combinatorics and Ordered Sets , Amer. Math. Soc. (1986) pp. 33–74 |
[a4] | G.-C. Rota, "On the foundations of combinatorial theory I: Theory of Möbius functions" Z. Wahrsch. Verw. Gebiete , 2 (1964) pp. 340–368 |
Möbius inversion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=M%C3%B6bius_inversion&oldid=23416