Title: On 0-1 polytopes with many facets

A 0-1 polytope is the convex hull of some 0-1 vectors from n-space. Properties of 0-1 polytopes, especially structured ones, play an important role in combinatorial optimization. A concise description of the facets, or defining inequalities, of such a polytope is the clue to solving the underlying integer programming problem. How many facets can such a polytope have? Write g(n) for the maximum number of facets a 0-1 polytope can have. It is not hard to see that g(n) < 2n!, and a simple construction shows that g(n)>2ⁿ. In this talk I give a construction showing that g(n) > (cn / log n)^n/4, which is the first superexponential bound on g(n). The construction is a random 0-1 polytope. This is joint work with Attila Pór.