**THE ELISHA NETANYAHU
INSTITUTE FOR ADVANCED STUDIES IN MATHEMATICS**

**invites you to a**

**SPECIAL
LECTURE SERIES**

**to be presented by**

Professor Jiri
Matousek

*Charles University, Prague*

The lectures will be held in

**Room 232
Amado Mathematics Building
Technion - Israel Institute of Technology
Haifa, Israel**

Lecture I: Monday, 11 March 2002—15:30

**KNESER'S CONJECTURE: MANY PROOFS AND ONE**

Kneser's conjecture, perhaps more appropriately called the
Lovasz-Kneser Theorem, states that for *n>2k*, the *k*-element subsets of *{1,2,...,n}*
cannot be colored by fewer than *n*-2*k*+2 colors so that no two disjoint *k*-tuples
receive the same color. Over the years, several proofs have been found (all based on the
Borsuk-Ulam theorem in topology or on variations of it); many of them imply somewhat
stronger results. The plan is to present an overview of these proofs and indicate one
that, in a sense, is the strongest, implying the consequences of all the others.

Lecture II: Wednesday, 13 March 2002—15:30

**ON LIPSCHITZ SUBSETS IN R**^{d}

Some years ago, Laczkovich asked the following
nice question in geometric measure theory: Does there exist, for every subset *E* of **R**^{d} of
positive Lebesgue measure, a Lipschitz map *f* from **R**^{d} to **R**^{d} that maps *E* onto a cube? A positive answer for *d=2* was
obtained by Preiss, and a different proof was given by the speaker, based on a
combinatorial statement. We discuss
higher-dimensional generalizations of that combinatorial statement, which seem interesting
in their own right.

Lecture III: Thursday, 14 March 2002—15:30

**UNIQUE-SINK ORIENTATIONS OF CUBES**

The *n*-cube is considered as a graph (with vertex set {0,1}^{n}
). A unique-sink orientation (USO) is an orientation of the edges of the *n*-cube
such that every face of the cube has exactly one sink (directed cycles are allowed). Such
orientations arise from several sources, such as linear programs (considering a generic
linear function on a polytope isomorphic to the cube), certain linear complementarity
problems, and certain convex programs. Algorithms have been studied for finding the global
sink in a USO; the USO is specified by an oracle that, given a vertex, returns the
orientation of the edges incident to that vertex. Upper and lower bounds for the
complexity of such algorithms have recently been given by Welzl, Szabo and Schurr;
improving them significantly is the main challenge. The speaker has proved that the number
of USO is 2^{Theta( 2^n log n)} . The number of acyclic USO is easily seen
to be between 2^{Omega(2^n)} and 2^{O(2^n log n)} ; it
would be nice to find better bounds.