printable pdf
比利时vs摩洛哥足彩 ,
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

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