simplify deciding evasiveness for many graph properties.

The best general result known to date on this topic is the following theo-

rem of Je¬ry Kahn, Michael Ezra Saks (b. 1956) and Dean Grant Sturtevant

63

(b. 1955) from 1984:

Kahn“Saks“Sturtevant Theorem. The evasiveness conjecture is true

for graphs on pk nodes, for any prime number p and integer k ≥ 1.

This veri¬es the conjecture for in¬nitely many values of n, the number of

nodes, but leaves it open when n is the product of at least two distinct primes.

Thus, the smallest values of n left open are 6, 10, 12, 14, 15, ...; however the

case of n = 6 was also veri¬ed by Kahn et al.. The general conjecture remains

open, beginning with the case n = 10.

The proof of Kahn et al. makes surprising use of topology. The key

idea is to view a monotone graph property for graphs on n vertices as a

simplicial complex with a high degree of symmetry, to whose associated space

a topological ¬xed point theorem can be applied. Here is how.

We will keep in mind some particular monotone graph property P and

consider graphs on the nodes 1, 2, ..., n. Such a graph is speci¬ed by the pairs

(i, j) of nodes that are connected by an edge. Let us take the set of these

pairs as the ground set for a set family ∆P , whose members are the edge-sets

n

of graphs not having property P. The set family ∆P is closed under taking

n

subsets, since monotonicity implies that removal of edges from a graph that

doesn™t have property P cannot produce a graph having that property.

Let us illustrate the idea for the case n = 4, taking as our monotone

property connectedness. There are 6 possible edges in a graph on the nodes

1, 2, 3, 4; see Figure 10.

2 3

w w

d

d

d

d

d

d

d

w dw

1 4

Figure 10: The 6 edges spanned by 4 nodes

64

The simplicial complex ∆conn of disconnected graphs on four vertices is

4

shown in Figure 11.

13 23

34

12

14 24

Figure 11: The complex of disconnected graphs on 4 nodes

In the rubber-sheet model depicted it consists of 4 triangles and 3 edges

(curved line segments) glued together. To understand this picture the reader

should think how to translate the vertices, edges and triangles of ∆conn into

4

disconnected graphs. For instance, the edge between 14 and 23 in Figure 11

corresponds to the disconnected graph

2 3

w w

w w

1 4

and the triangle with vertices 13, 14 and 34 corresponds to the disconnected

graph

65

2 3

w w

w w

1 4

Observe in Figure 11 that the space represented by the complex ∆conn has

4

conn

many holes ” in the terminology used before this means that ∆4 has some

nonzero Betti numbers. It turns out to be a general fact, not hard to prove,

that if the property P is not evasive then ∆P is acyclic, meaning that all

n

P

Betti numbers of ∆n are equal to zero.

There are several theorems in topology to the e¬ect that certain mappings

f of an acyclic space to itself must have ¬xed points, i.e. points x such that

f (x) = x. The best known one ” one of the classics of topology ” is

Luitzen Egbertus Jan Brouwer™s (1881“1966) theorem from 1904, which says

that every continuous mapping of an n-dimensional ball to itself has a ¬xed

point. The one needed for the present application is a ¬xed point theorem

of Robert Oliver (b. 19??) from 1975, which (stripped of some technical

details) says that for certain groups G of symmetry mappings of an acyclic

simplicial complex ∆ to itself there is a point x in the associated space such

that f (x) = x for all mappings f in G.

The complex ∆P of a monotone graph property has a natural group of

n

symmetries, namely the symmetric group Sn of all permutations of the set

of nodes 1, 2, ..., n. Permuting the nodes amounts to a relabeling (node i

gets relabeled f (i), etc.), and it is clear that such a relabeling will not a¬ect

whether the graph in question has property P. Therefore every permutation

of 1, 2, ..., n induces a self-symmetry of the complex ∆P of graphs not having

n

property P.

The pieces needed for the proof of Kahn et al. are now at hand. Here is

how they argued.

Suppose P is a monotone property for graphs on n nodes that is not

66

evasive. Then, as was already mentioned, the associated complex ∆P is n

k

acyclic. If furthermore n = p then due to some special properties of prime-

power numbers (the existence of ¬nite ¬elds) one can construct a subgroup

G of Sn having the special properties needed for Oliver™s ¬xed point theorem.

Hence there is a point x in the space associated to ∆P such that f (x) = x for

n

all permutations f in G. However, this means that there is a nonempty set

A in the complex ∆P (that is, a graph with edge-set A not having property

n

P ) such that f (A) = A for all f in G. Since G is transitive (meaning that if

u and v are two vertices of ∆P then u = f (v) for some mapping f in G), A

n

must consist of all vertices of ∆P ; that is, A is the complete graph. We have

n

obtained that the complete graph on nodes 1, 2, . . . , n does not have property

P , and since P is monotone that means that no graph on 1, 2, . . . , n can have

property P , so P is trivial.

The argument shows that for monotone P nonevasive implies trivial, or

which is logically the same: nontrivial implies evasive.

Viewing a graph property (such as connectedness) as a simplicial complex

and submitting it to topological study may seem strange. One can wonder if

this point of view is of any value other than ” by remarkable coincidence ”

for the evasiveness conjecture. It has recently become clear that this is indeed

the case. Namely, the complexes ∆conn of disconnected graphs on n vertices

n

have arisen and play a role in the work of Victor Anatol™evich Vassiliev (b.

1956) on knot invariants. Also some other monotone graph properties have

naturally presented themselves as simplicial complexes in other mathematical

contexts.

11 Complexity of sorting and distinctness

The following is a very basic situation studied in complexity theory. A string

of real numbers x1 , x2 , . . . , xn is given. A computer is asked to decide some

property of the sequence or to restructure it using only pairwise comparisons.

This means that the computer is allowed to learn about the input sequence

only by inspecting pairs xi and xj and deciding whether xi > xj , xi <

xj or xi = xj . The question then is: How many such comparisons must

67

the computer make in the worst case when using the best algorithm? This

number, as a function of n, is called the complexity of the problem.

The following notation is used to state such results. To say that the

complexity is ˜(f (n)), where f (n) is some function, means that there exist

constants c1 and c2 such that

c1 · f (n) < complexity < c2 · f (n).

While this notation doesn™t give the exact numerical value of the complexity

(which is often hard, if not impossible, to determine) it reveals its order of

growth, which is what is usually taken as the main indication if a problem is

computationally easy or hard. In the following formulas the function “log n”

will frequently appear. Readers not familiar with the logarithm function can

take this to mean roughly the number of digits needed to write the number

n in base 10, so that for instance log 1997 ≈ 4.

Here are some basic and well-known examples.

1. Sorting. To rearrange the n numbers increasingly xi1 ¤ xi2 ¤ · · · ¤

xin requires ˜(n log n) comparisons.

2. Median. To ¬nd j such that xj is “in the middle”, meaning that half

of the xi ™s are less than or equal to xj and half of the xi ™s are greater

than or equal to xj , requires ˜(n) comparisons. In fact, it has been

shown that 2n comparisons are needed and that 3n comparisons su¬ce.

3. Distinctness. To decide whether all entries xi are distinct, that is

whether xi = xj when i = j, requires ˜(n log n) comparisons.

The problem we wish to discuss, which was only recently resolved, is a

generalization of the distinctness problem. Namely,

k-equal problem: for k ≥ 2, decide whether some k entries are equal, that

is, can we ¬nd i1 < i2 < · · · < ik such that xi1 = xi2 = · · · = xik ?

For example, are there nine equal entries in the following list of numbers?

68

2479137468584871395519674234615946331486772955924362854117836972581932

Answer: Yes, there are nine copies of the number “4”. Are there ten equal

entries? Answer: No. If pairwise comparisons are the only type of operation

allowed, how should one go about settling these questions in an e¬cient

manner, and how many comparisons would be needed?

Here are a few immediate observations. If k = 2 the problem reduces to

the distinctness problem, so the complexity is ˜(n log n). At the other end of

the scale, if k > n the complexity is ˜(n), because we can argue as follows.

2

The median xj can be found using 3n comparisons. If there are k > n 2

equal entries then the median must be one of them. Thus after comparing

xj with the other n ’ 1 entries xi we gain enough information to conclude

whether there are some k entries that are equal. This procedure requires in

all 4n ’ 1 comparisons. On the other hand it is easy to see that at least n ’ 1

comparisons are needed in the worst case, so there are both upper and lower

bounds of the form “constant times n” to the complexity.

We have seen that the complexity of the k-equal problem decreases from

˜(n log n) to ˜(n) when the parameter k grows from 2 to above n , so the

2

k-equal problem seems to get easier the larger k gets. The exact form of this

relationship is given in the following result from 1992 of Anders Bj¨rner (b.

o

1947), L´szl´ Lov´sz and Andrew Chi-Chih Yao (b. 1946).

ao a

Theorem. The complexity of the k-equal problem is ˜(n log 2n ).

k

The upper bound is obtained via a partial sorting algorithm based on re-

peated median-¬nding. It generalizes what was described for the case k > n

2

above. We shall leave it aside.

The lower bound ” proving that at least n log 2n comparisons are needed

k

(up to some constant) by every algorithm in the worst case ” is the di¬cult