Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 295 - Mathematics Colloquium

Dimitris Gatzouras

Agricultural Univ. of Athens, Greece (visiting UCSD)

Lower bound for the maximal number of facets of a $-1/1$-polytope

Abstract:

A $-1/1$-polytope in $\Bbb{R}^n$ is, by definition, the convex hull of a subset of the vertices of the unit cube $[-1,1]^n.$ Let $g(n)$ denote the maximal number of facets such a polytope can have. Fukuda and Ziegler asked how $g(n)$ grows with $n.$ Fleiner, Kaibel and Rote have shown that $g(n)\leq 30 (n-2)!$ for sufficiently large $n,$ and this is the best known upper bound on $g(n).$ In a major advancement, B\'{a}r\'{a}ny and P\'{o}r obtained the lower bound $g(n)\geq (c n/\ln n)^{n/4},$ where $c>0$ is a universal constant, and gave heuristics of why one might expect $g(n)$ to be of the order of $n^{n/2}$ (this is believed to be the right order of magnitude for $g(n)$). We show that $g(n)\geq (cn/\ln n)^{n/2},$ with $c>0$ a universal constant.

Host: Dimitris Politis

May 19, 2005

4:00 PM

AP&M 6438

****************************