no holes of other dimensions. The torus has Betti numbers (0, 2, 1) because

there are two essentially di¬erent 1-dimensional holes (corresponding to the

circles a and b in Figure 7) and one 2-dimensional hole (the interior). Note

that the two circles a and b are genuine “holes” in the sense that they cannot

be continuously deformed to single points within the torus, and that they are

“di¬erent” holes since one cannot be continuously deformed into the other.

The concept of a 0-dimensional hole is perhaps not so clear on an intuitive

level, but having β0 = 0 means that the space hangs together in one piece (is

connected), and in general β0 (T ) + 1 is the number of connected components

of the space T . (Note to specialists: Our βi (T )™s are really the reduced

Betti numbers of T , di¬ering from the “ordinary” Betti numbers only in that

β0 (T ) + 1 rather than β0 (T ) is the number of connected components of T .)

We have seen that ¬nite set systems are of use in topology as encodings

of topological spaces. But the connection between spaces and simplicial com-

plexes opens up a two-way street. What if the mathematics we are doing

deals primarily with ¬nite set systems, as is often the case in combinatorics?

For instance, say that a combinatorial problem we are dealing with involves

the fourteen 3-element sets listed in (25). Could the properties of the asso-

ciated topological space ” the torus ” be of any relevance? For instance,

could its Betti numbers (measuring the number of “holes” in the space) have

something useful to say about the set system as such? We will show that

this may indeed be the case, and this is in fact one of the cornerstones for

the “topological method” in combinatorics.

57

The idea to use topological reasoning in combinatorics is quite old but had

a somewhat unfortunate start. It seems to have ¬rst occurred in connection

with a famous problem of Euler. The following con¬guration is called a

Graeco-Latin square of order n: An n — n-matrix of ordered pairs (a, b) of

numbers a and b from 1, 2, ..., n such that the ¬rst entries a are distinct in

every row and column, the second entries b are distinct in every row and

column, and all n2 possible pairs occur. For instance, here is a Graeco-Latin

square of order 3:

1, 1 2, 2 3, 3

2, 3 3, 1 1, 2

3, 2 1, 3 2, 1.

Euler stated without proof in his paper “Recherches sur une esp`ce de

e

carr´s magique” from 1782 that such con¬gurations cannot exist for n =

e

6, 10, 14, 18, .... His claim was proven correct for n = 6 by G. Tarry (18??“

19??) in 1901. In 1922 Harris F. MacNeish (18??“19??) published a paper

in Annals of Mathematics supposedly proving Euler™s claim for all remaining

values of n. His argument, which was based on topology, was unfortunately

incorrect. In fact, subsequent research has shown that Euler™s claim itself is

false, except for the single case of n = 6 !

After this unsuccessful start it took a long time before the idea resurfaced

” topological proofs for combinatorial results have come to the fore only in

the last two decades. Let us now go on to see a couple of concrete examples.

BOX: Borsuk and combinatorics

The Polish mathematician Karol Borsuk (1905“1982) made some fun-

damental contributions to the early development of topology. In 1933 he

published a paper entitled (in translation) “Three theorems about the n-

dimensional euclidean sphere”. That paper contains, among other wonderful

58

things, a famous theorem and a famous open problem. Let us state them

(within this box we will assume familiarity with the topological terminology

used).

Borsuk™s Theorem. If the k-dimensional sphere is covered by k + 1 closed

sets, then one of these sets must contain a pair of antipodal points.

Borsuk™s Problem. Is it true that every set of diameter one in k-dimensional

real space Rk can be partitioned into at most k + 1 sets of smaller diameter?

This work of Borsuk has interacted with combinatorics in a remarkable

way. In 1978 L´szl´ Lov´sz (b. 1948) solved a di¬cult combinatorial problem

ao a

” the “Kneser Conjecture” from 1955 ” by using Borsuk™s theorem. Then,

in 1992 the debt to topology was repaid when Je¬ry Ned Kahn (b. 1950)

and Gil Kalai (b. 1955) solved Borsuk™s problem using some results from

pure combinatorics. By stating the relevant results on the combinatorial

side we hope to give a small glimpse of these interactions, which are quite

unexpected.

The answer to Borsuk™s problem is de¬nitely “yes” when k = 1, the

statement then comes down to dividing a line segment of length 1 into two

shorter segments, which is clearly possible. It was also long known that the

statement is true for k = 2 and k = 3, and it was generally believed that

the statement is true for all dimensions k ” this became known as Borsuk™s

conjecture.

It therefore came as a great surprise that the answer to Borsuk™s prob-

lem is actually “no”, contrary to what “everyone” had believed for nearly

60 years. But one has to go to very high dimensions (k ≈ 1, 000) to ¬nd

counterexamples with the Kahn-Kalai method. The problem is still open for

k = 4.

The combinatorial result from which the solution to Borsuk™s problem

follows is this 1981 theorem of Peter Frankl (b. 19??) and Richard Michael

Wilson (b. 1945).

Frankl-Wilson Theorem. Let k be a power of a prime number, and let F

be a family of 2k-element subsets of {1,2,. . . ,4k} such that no two members

59

4k’1

of F have k elements in common. Then F has at most 2 · members.

k’1

The Kneser conjecture ” now a theorem of Lov´sz ” is the following

a

statement:

Lov´sz™ Theorem. If the n-element subsets of a (2n + k)-element set are

a

partitioned into k + 1 classes, then some class will contain a pair of disjoint

n-element sets.

The details of how this conclusion is derived from Borsuk™s theorem, as

well as the argument for solving Borsuk™s problem using the Frankl-Wilson

theorem, must unfortunately be left aside. See the suggested reading for

further information.

10 Complexity of graph properties.

A major theme in theoretical computer science is to estimate the complex-

ity of computational tasks. By “complexity” is here meant the amount of

time and of computational resources needed. By constructing algorithms one

shows that a task can be done in a certain number of steps. It is often the

more di¬cult part to show that there is no “faster” way, i.e. requiring fewer

steps.

Examples of this will be given in this and the following section. We

begin by considering algorithms that test whether graphs have a certain

given property P. For example, P could be the property of being connected,

meaning that you can get from any node to any other node by walking along

a path of edges. The left graph in Figure 9 is connected whereas the right

one is disconnected, since there is no way to get from nodes 1, 2 or 3 to nodes

4 or 5.

Connectedness is a very basic property of graphs which can be decided

60

2u 3 2u 3

u u

d

d

4 4

d u u

D D

d

D D

d

D D

u du

D

u D

u

1 5 1 5

Figure 9: A connected and a disconnected graph

at a glance on small examples represented as a drawing. But say you have

a graph with 1 million nodes, coming perhaps from a communications net-

work or a chip design, which is presented only as a list of edges (adjacent

pairs of nodes) ” then it is not quite so clear what to do if one wants to

decide whether the graph is connected, making e¬cient use of computational

resources. Among the interesting questions one can ask is whether it is pos-

sible to decide connectedness of the graph without checking for all possible

pairs of nodes (there are nearly 500 billion of them) whether they are edges

of the graph or not? If this were so it could conceivably lead to valuable

saving of time and resources.

A basic general question to ask then is this: For a given property P of

graphs, is there some algorithm that decides for every graph G whether it

has property P without knowing for every pair of nodes whether they span

an edge of G or not? If this is not the case, i.e. if every P-testing algorithm

must for at least some graph have complete knowledge about all its edges,

then P is said to be an evasive property.

For instance, connectedness is an evasive property. To see this we can

argue as follows. Imagine that we have a computer running a program that

tests graphs for connectedness. The graphs to be tested, whose nodes we may

assume are labeled 1, 2, ..., n, are presented to the computer in the form of an

n — n upper-triangular matrix of zeros and ones, with a 1 entry in row i and

column j, for i < j, if (i, j) is an edge of the graph and a 0 entry otherwise.

61

For instance, here are the matrices representing the graphs in Figure 9:

—100 0 —110 0

—10 1 —10 0

—0 1 —0 0

— 1 — 1

— —

The computer is allowed to inspect only one entry of this matrix at a time,

and what we want to show is that for some graph it must in fact inspect

all of them. To ¬nd such a worst-case graph we can imagine playing the

following game with the computer. Say that instead of deciding on the graph

in advance, we write the zeros and ones specifying its nonedges and edges

into the matrix only at the last moment, as the computer demands to inspect

them. Say furthermore that we do this according to the following strategy:

When the computer goes to inspect the (i, j) entry of the matrix (according

to whatever algorithm it is using), then

• write 0 into position (i, j) if it is not possible to conclude from the

partial information known to the computer at that time ” including

this last 0 ” that the graph is disconnected,

• otherwise, write 1 into position (i, j).

It is an elementary but somewhat tricky argument to show that this

strategy will force the computer to inspect all entries of the matrix before

it can decide whether the corresponding graph is connected or not. We will

now outline a proof for readers who are developing a taste for combinatorial

reasoning, and who understand what is meant by a proof by ¬nite induction.

The crucial step will be to prove the following statement: Suppose that at

some stage 1 is written into position {i, j}. Let A be the set of nodes that are

at that stage connected to i by 1-marked edges, and let B be the set of nodes

connected to j by 1-marked edges. Then all possible edges between nodes in

A ∪ B have been inspected at that stage. Note that A © B = ˜, and that

|A∪B| ≥ 2 since i ∈ A and j ∈ B. The statement is clearly true if |A∪B| = 2,

and we proceed by induction on |A ∪ B|, that is, the number of elements of

A ∪ B. Suppose that |A ∪ B| > 2. Since 1 (and not 0) is written into position

62

{i, j} that means that there is some partition C ∪ D = {1, 2, . . . , n} into

nonempty disjoint subsets C and D such that i ∈ C , j ∈ D and all possible

edges {c, d} with c ∈ C , d ∈ D and {c, d} = {i, j} are already marked

with 0. Clearly, we must have A ⊆ C and B ⊆ D, so in particular all edges

between a node in A and a node in B have already been inspected. Also, all

edges between two nodes both in A have by the induction assumption been

inspected, and similarly for B. This covers all possible edges between nodes

in A ∪ B and the claim follows.

Suppose now that connectedness/disconnectedness can be decided after

inspection of k matrix entries, and that k is the minimum such number.

According to our strategy for writing 0 or 1, the outcome can never be

that the graph is disconnected. Also, if the kth entry is 0 and the graph

is connected we have a contradiction, since then the information needed to

conclude connectedness would have been available already before the kth

entry was inspected. So, the kth entry is 1, and since the conclusion is that

the graph is connected the claim above implies that all other entries have

already been inspected before the kth one. This proves that connectedness

is an evasive graph property.

It has been decided for many graph properties whether they are evasive. It

turns out that among the evasive ones are many that are monotone, meaning

that if the property holds for some graph then it will also hold if more edges

are added. For instance, connectedness is an example of a monotone property.

Mounting evidence from work in the late 1960™s by several researchers led to

the following conjecture.

Evasiveness Conjecture. Every monotone nontrivial graph property is

evasive.

By “nontrivial” is here meant that there is at least one graph that has the

property and one that doesn™t. Since monotonicity is usually completely