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.