<<

. 10
( 14 .)



>>

trivial to verify whereas evasiveness is not, this conjecture ” if true ” would
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
 
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

<<

. 10
( 14 .)



>>