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

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