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 200215: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 200215: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 200215: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.