Low-dimensional faces of random 0/1-polytopes
| dc.creator | Kaibel, Volker | |
| dc.date | 2003-11-21 | |
| dc.date | 2004-02-25 | |
| dc.date.accessioned | 2026-07-07T05:03:10Z | |
| dc.date.available | 2026-07-07T05:03:10Z | |
| dc.description | Let P be a random $d$-dimensional 0/1-polytope with $n(d)$ vertices, and denote by $ϕ_k(P)$ the \emph{$k$-face density} of $P$, i.e., the quotient of the number of $k$-dimensional faces of $P$ and $\binom{n(d)}{k+1}$. For each $k\ge 2$, we establish the existence of a sharp threshold for the $k$-face density and determine the values of the threshold numbers $τ_k$ such that, for all $ε>0$, $$ E(ϕ_k(P)) = \begin{cases} 1-o(1) & \text{if $n(d)\le 2^{(τ_k-ε)d}$ for all $d$} o(1) & \text{if $n(d)\ge 2^{(τ_k+ε)d}$ for all $d$} \end{cases} $$ holds for the expected value of $ϕ_k(P)$. The threshold for $k=1$ has recently been determined in \texttt{math.CO/0306246}. In particular, these results indicate that the high face densities often encountered in polyhedral combinatorics (e.g., for the cut-polytopes of complete graphs) should be considered more as a phenomenon of the general geometry of 0/1-polytopes than as a feature of the special combinatorics of the underlying problems. | |
| dc.description | 15 pages, to appear in: Proceedings IPCO X, Jun 9-11, 2004, Columbia University, New York. Changes in the revised version: Slightly improved main result, several minor changes in the presentation, appendix removed | |
| dc.identifier | https://arxiv.org/abs/math/0311393 | |
| dc.identifier | http://arxiv.org/abs/math/0311393 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69304 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | Probability | |
| dc.subject | 52B12; 52B05; 90C57; 60C05 | |
| dc.title | Low-dimensional faces of random 0/1-polytopes | |
| dc.type | text |