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-2k+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 Rd

Some years ago, Laczkovich asked the following nice question in geometric measure theory: Does there exist, for every subset E of Rd of positive Lebesgue measure, a Lipschitz map f from Rd to Rd 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 2Theta( 2^n log n) . The number of acyclic USO is easily seen to be between 2Omega(2^n) and 2O(2^n log n) ;  it would be nice to find better bounds.