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
****************************