Jesus De Loera

University of California - Davis

The Convex Geometry of Tables and Arrays

Tuesday, March 26, 2013

4:00–5:00PM

008 Kemeny Hall

Abstract: In this talk we introduce the audience to convex bodies that consists of all multidimensional arrays of nonnegative numbers that satisfy certain sum conditions on subsets of the entries. They are among the first ever studied combinatorial optimization problems, going back to the 1930's work of Kantorovich and Koopmans (who received the Nobel prize of Economics for it). These convex sets are known under various names: e.g., transportation polytopes in optimization or contingency tables in statistics, etc. They have interest also in pure mathematics since permutation matrices, latin squares, magic squares, and sudoku arrangements, appear as lattice points or vertices of these polytopes.

In this talk I will survey advances and challenges on the understanding of the combinatorics and geometry of these polyhedra. In particular, I will report on the following "universality theorem": Every rational convex polytope is strongly isomorphic to a 3-way, 2-margin transportation polytope. This has very interesting consequences for integer programming and statistics. It is indeed useful to the solution of several open questions collected in the 1984 monograph by Yemelichev-Kovalev-Kravtsov and the 1986 survey paper of Vlach. For young people I will try to state several open questions, including some beautiful challenges proposed by John G. Kemeny in the 1950's.

Based on joint papers with Ed Kim, Fu Liu, Francisco Santos and Shmuel Onn and a forthcoming survey paper.

My Favorite Open Problems about Polyhedra

Wednesday, March 27, 2013

7:00–8:00PM

008 Kemeny Hall

Abstract: TConvex polyhedra are familiar objects. Cubes and pyramids are common in all kindergartens. Polyhedra, in their high-dimensional versions, are widely used in applied mathematics. Their beauty and simplicity appeal to all, but very few people know of the many easy-to-state but difficult-to-solve mathematical problems that hide behind their beauty.This lecture introduces the audience to some fascinating open questions on the frontiers of mathematical research and its applications.

NB: A PDF version of this announcement (suitable for posting) is also available.

Algebraic and Geometric Ideas in the Theory of Linear Optimization

Colloquium talk

Thursday, March 28, 2013

4:00–5:00PM

007 Kemeny Hall

Abstract: Linear optimization is undeniably a central tool of applied mathematics with applications in a wide range of topics, from statistical regression to image processing. The theory of linear optimization has many beautiful geometric and algebraic topics and it is a source of many fascinating mathematical problems.

In this talk I will present several advances from the past 5 years in the theory of linear optimization. These results include new results on the complexity of the simplex method, the structure of central paths of interior point methods, and about the geometry of some less well-known iterative techniques. One interesting feature of these new theorems is that they connect this very applied algorithmic field with seemingly far away topics like algebraic geometry, differential geometry, and combinatorial topology.

This talk is geared for the non-expert and I wil summarize work by many authors, including results that are my own joint work with subsets of the following people A. Basu, M. Junod, S. Klee, B. Sturmfels, and C. Vinzant.