2004 | OriginalPaper | Buchkapitel
Low-Dimensional Faces of Random 0/1-Polytopes
verfasst von : Volker Kaibel
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let P be a random 0/1-polytope in ℝd with n(d) vertices, and denote by ϕ k (P) the 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≥ 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, $$ {\mathbb{E}}[\varphi_k(P)]\ =\ \begin{cases} 1-{\mathrm o}(1) & \text{ if $n(d)\le 2^{(\tau_k-\varepsilon)d}$ for all~$d$} \\ {\mathrm o}(1) & \text{ if $n(d)\ge 2^{(\tau_k+\varepsilon)d}$ for all~$d$} \\ \end{cases} $$ holds for the expected value of ϕ k (P). The threshold for k=1 has recently been determined in [1].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.