|
|||||
|
|
Lower Bound for the Maximal Number of Facets of a 0/1 Polytope |
|
| Authors: | Dimitris Gatzouras Giannopoulos Apostolos Nikolaos Markoulakis |
| Institution: | (1) Department of Mathematics, Agricultural University of Athens, Iera Odos 75, 118 55 Athens, Greece;(2) Department of Mathematics, University of Athens, Panepistimiopolis, 157 84 Athens, Greece;(3) Department of Mathematics, University of Crete, Heraklion 714 09, Crete, Greece |
| Abstract: | Let $f_{n-1}(P)$ denote the number of facets of a polytope $P$ in ${\Bbb R}^n$. We show that there exist 0/1 polytopes $P$ with $$f_{n-1}(P)\geq\left (\frac{cn}{\log^2 n}\right )^{n/2},$$ where $c>0$ is an absolute constant. This improves earlier work of Barany and Por on a question of Fukuda and Ziegler. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |