<<

. 12
( 14 .)



>>

 
t t
ddt  
b rr cd  
r
rr d  
rrd  
rd  
rd
rt
 
a
Figure 14: A small poset

The M¨bius function µ(x) is recursively de¬ned for any ¬nite poset as
o
follows: Put µ(x0 ) = 1 for the bottom element x0 of the poset, then require


75
that
µ(x) = ’ µ(y)
y<x

for all other elements x. This formula means that we are to de¬ne µ(x) so
that when we sum µ(y) for all y less than or equal to x the resulting sum
equals zero. This can clearly be done as long as one knows the values µ(y) for
all elements y less than x. The reader can see how this recursive de¬nition
works by computing the M¨bius function of the poset in Figure 14, starting
o
from the bottom. We get recursively:

µ(a) = 1, by de¬nition,
µ(b) = ’µ(a) = ’1,
µ(c) = ’µ(a) = ’1,
µ(d) = ’µ(a) = ’1,
µ(e) = ’µ(a) = ’1,
µ(f ) = ’µ(a) ’ µ(b) ’ µ(c) ’ µ(d) = ’1 + 1 + 1 + 1 = 2,
µ(g) = ’µ(a) ’ µ(d) = ’1 + 1 = 0,
µ(h) = ’µ(a) ’ µ(b) ’ µ(c) ’ µ(d) ’ µ(e) ’ µ(f ) ’ µ(g)
= ’1 + 1 + 1 + 1 + 1 ’ 2 ’ 0 = 1.

Figure 15 shows the same poset with computed M¨bius function values.
o

The M¨bius function has its origin in number theory, where it was intro-
o
duced by August Ferdinand M¨bius (1790“1868). (M¨bius is best known to
o o
nonmathematicians for his eponymous connection with the “M¨bius strip.”
o
The M¨bius strip itself was well-known long before M¨bius, but M¨bius was
o o o
one of the ¬rst persons to systematically investigate its mathematical prop-
erties.) The posets relevant to number theory are subsets of the positive
integers ordered by divisibility. For instance, see the divisor diagram of the
number “60” in Figure 16. A calculation based on this diagram, analogous
to the one we just carried out over Figure 14, will show that µ(60) = 0. In
the case of the classical M¨bius function of number theory there is however a
o
faster way to compute. Namely, for n > 1 one has that µ(n) = 0 if the square
of some prime number divides n, and that otherwise µ(n) = (’1)k where k
is the number of prime factors in n. Hence, for example: µ(60) = 0 since
22 = 4 divides 60; and µ(30) = ’1 since we have the prime factorization
30 = 2 · 3 · 5 with an odd number of prime factors.


76
t1
 d
 d
d
 
d
2t   0t d
 
d
 d
d
  d
dt -1
  d  
  d  
 
t t
-1 t
d  
-1 rr -1 d  
rr
d  
rr d  
rr
d  
rrt
d 1

Figure 15: Values of the M¨bius function
o

The M¨bius function is very important in number theory. Let it suf-
o
¬ce to mention ” for those who have the background to know what we are
referring to ” that both the Prime Number Theorem and the Riemann Hy-
pothesis (considered by many to be the most important unsolved problem in
all of mathematics) are equivalent to statements about the M¨bius function.
o
n
Namely, letting M (n) = k=1 µ(k), it is known that


M (n)
Prime Number Theorem ⇐’ lim = 0,
n
n’∞

Riemann Hypothesis ⇐’ |M (n)| ¤ n1/2+ , for all > 0 and all su¬ciently large n.

The M¨bius function is an indispensable tool in enumerative combina-
o
torics because it can be used to “invert” summations over a partially ordered
index set. Here is a statement of the “M¨bius inversion formula” in a special
o
case. If a function f : P ’ Z from a poset P to the integers is related to
another function g : P ’ Z by the partial summation formula

f (x) = g(y),
y≥x



77
60



12 20 30


4 6 10 15



2 3 5



1


Figure 16: The divisors of “60”.

then the value g(x0 ) at the bottom element x0 of P can be expressed in terms
of f via the formula
g(x0 ) = µ(y)f (y).
y∈P



The M¨bius function also has a topological meaning, which is the reason
o
it turns up in “Fact 2” of this section. The connection is as follows. Let P be
a poset with bottom element b and top element t. De¬ne the set family ∆(P )
to consist of all chains (meaning: totally ordered subsets) x1 < x2 < · · · < xk
in P = P \{b, t}, meaning P with b and t removed. Then ∆(P ) is a simplicial
complex (since a subset of a chain is also a chain), so as discussed in Section
9 there is an associated topological space.

For instance, let P be the divisor poset of the number “60” shown in
Figure 16. Then P = P \ {1, 60} has the following twelve maximal chains


2 ” 4 ” 12
2 ” 4 ” 20

78
2 ” 6 ” 12
2 ” 6 ” 30
2 ” 10 ” 20
2 ” 10 ” 30
3 ” 6 ” 12
3 ” 6 ” 30
3 ” 15 ” 30
5 ” 10 ” 20
5 ” 10 ” 30
5 ” 15 ” 30

As was explained in Section 9 these twelve triples of the simplicial complex
should be thought of as describing twelve triangles that are to be glued
together along common edges. This gives the topological space shown in
Figure 17 ” a 2-dimensional disc.

20 5

10

2 30
4 15

6



12 3

Figure 17: The simplicial complex of proper divisors of “60”.

So, what does all this have to do with the M¨bius function? The relation
o
is this. Let βi (P ) be the ith Betti number of the simplicial complex ∆(P ),
and let µ(P ) denote the value that the M¨bius function attains at the top
o
element of P . Then,
µ(P ) = β0 (P ) ’ β1 (P ) + β2 (P ) ’ β3 (P ) + · · · . (28)

79
For instance, the space depicted in Figure 17 is a disc. The important
thing here is that this space has no holes of any kind. Hence, all Betti
numbers βi (P ) are zero, implying via formula (28) that µ(P ) = 0. This
“explains” topologically why µ(60) = 0, a fact we already knew from simpler
considerations. On the other hand, if P is the divisor diagram of “30” (which
can be seen as a substructure in Figure 16), then ∆(P ) is the circle 2 ” 6
” 3 ” 15 ” 5 ” 10 ” 2 (a substructure in Figure 17). This circle has
a one-dimensional hole, so β1 (P ) = 1. All other Betti numbers are zero,
hence formula (28) gives that µ(30) = ’1, another fact we have already
encountered.




12 Face numbers of polytopes

Among the many results of Euler that have initiated fruitful lines of develop-
ment in combinatorics, the one that is perhaps most widely known is “Euler™s
formula” for 3-dimensional polytopes from 1752. It goes as follows.

A 3-polytope P (or, 3-dimensional convex polytope, to be more precise) is
for a mathematician a bounded region of space obtained as the intersection
of ¬nitely many halfspaces (and not contained in any plane). For the layman
it can be described as the kind of solid body you can create from a block
of cheese with a ¬nite number of plane cuts with a knife. For instance,
take the ordinary cube shown in Figure 18 ” it can be cut out with six
plane cuts. The cube is one of the ¬ve Platonic solids: tetrahedron, cube,
octahedron, dodecahedron and icosahedron, known and revered by the Greek
mathematicians in antiquity.

A polytope that is dear to all combinatorialists is the “permutohedron”,
shown in Figure 19. Its 24 corners correspond to the 24 = 4 · 3 · 2 · 1 permu-
tations of the set {1, 2, 3, 4}. The precise rule for constructing the permu-
tohedron and for labelling its vertices with permutations is best explained
in 4-dimensional space and will be left aside. Note that the pairs of permu-


80
Figure 18: The cube.

tations that correspond to edges of the permutohedron are precisely pairs
that di¬er by a switch of two adjacent entries, such as “2143 ” 2134” or
“3124 ” 3214”. Thus, edge-paths on the boundary of the permutohedron
are precisely paths consisting of such “adjacent transpositions”, giving geo-
metric content to the topic of reduced decompositions, that was discussed in
Section 6.

The boundary of a 3-polytope is made up of pieces of dimension 0, 1 and
2 called its faces. These are the possible areas of contact if the polytope is
made to touch a plane surface, such as the top of a table. The 0-faces are
the corners, or vertices, of the polytope. The 1-faces are the edges, and the
2-faces are the ¬‚at surfaces, such as the six squares bounding the cube. The
permutohedron has fourteen 2-faces, six of which are 4-sided and eight are
6-sided.

<<

. 12
( 14 .)



>>