SPECIAL LECTURE SERIES
by
VICTOR KLEE
University of Washington
The lectures will be held in
Room 232
Amado Mathematics Building
Technion - Israel Institute of Technology
Haifa, Israel
Lecture I: April 3, 2000 — 15:30
Some Unsolved Problems in High-Dimensional Discrete Geometry
For purposes of this talk, "high-dimensional" means in Euclidean space of dimension at least 4. The problems to be discussed do not require much background for understanding what is being asked, but nevertheless they remain unsolved despite the efforts of many mathematicians. I once thought it would be nice to have, for each dimension d between 2 and (say) 100, an intuitively appealing unsolved problem in discrete or convex geometry that is "essentially d-dimensional" in the sense that d is the largest or the smallest dimension in which the problem is still unsettled. I still think it would be nice, but I haven't made much progress toward the goal. However, I will be able to present problems that are essentially d-dimensional for at least the following values of d:
4, 5, 6, 7, 9, 14, 21, 28, 41, 427.
For each problem, I'll say something about what is known concerning it and why it is of interest. (Unsolved problems for d = 2 and d = 3 will be presented in a later lecture.)
Lecture II: April 5, 2000 — 16:30
Some Unsolved Problems in Low-Dimensional Intuitive Geometry
Here "low-dimensional" means in Euclidean space of 2 or 3 dimensions. "Intuitive" suggests that the statements of the problems are so easily understood that the problems should be easily solved. Nevertheless, the problems remain unsolved despite the efforts of many researchers, in some cases stretching over more than 50 years. Most of the problems are in discrete geometry or convex geometry.
For each of the problems to be presented, something will be said about the history of the problem and about known partial results. These appear to be problems whose solution should depend less on the development of elaborate machinery than on getting a really bright idea. (However, this appearance may be deceptive.)
Lecture III: April 6, 2000 — 15:30
The d-Step Conjectures
Consider a d-dimensional cube. It's a d-polytope with 2d facets ((d-1)-faces), and between any two vertices there's a path formed from d or fewer edges. In its simplest form, the "d-step conjecture" asserts that not only on the d-cube, but on each d-polytope with 2d facets, any two vertices can be joined by a path of d or fewer edges. The conjecture was formulated by W.M Hirsch in 1957 and reported by George Dantzig in his book of 1963. It remains the outstanding unsolved problem concerning the combinatorial structure of convex polytopes. It may also turn out to be relevant to the still-open question of whether, in the model of infinite-precision real arithmetic, the simplex algorithm for linear programming runs in polynomial time.
Over the years, several stronger versions of the d-step conjecture have been formulated. They are all correct for d = 3 but most of them have been disproved by counterexamples for values of d ranging from 4 to 11. However, a few of these stronger d-step conjectures are (like the original) still open. The purpose of this talk will to be to tell what is known about the original d-step conjecture and some of its relatives.