<<

. 9
( 14 .)



>>

¬‚ecting the fact that it has exactly one d-dimensional “hole” (its interior) and
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

<<

. 9
( 14 .)



>>