Low-dimensional faces of random 0/1-polytopes

Details Low-dimensional faces of random 0/1-polytopes Low-dimensional faces of random 0/1-polytopes

2003-11-21

arxiv.org/abs/math/0311393v2

Mathematics

Combinatorics

15 pages, to appear in: Proceedings IPCO X, Jun 9-11, 2004, Columbia University, New York. Changes in the revised version: Sli

Scientific paper

Let P be a random $d$-dimensional 0/1-polytope with $n(d)$ vertices, and denote by $\phi_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 $\tau_k$ such that, for all $\epsilon>0$, $$ E(\phi_k(P)) = \begin{cases} 1-o(1) & \text{if $n(d)\le 2^{(\tau_k-\epsilon)d}$ for all $d$} o(1) & \text{if $n(d)\ge 2^{(\tau_k+\epsilon)d}$ for all $d$} \end{cases} $$ holds for the expected value of $\phi_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.

Affiliated with

Also associated with

No associations

Rating

Low-dimensional faces of random 0/1-polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Low-dimensional faces of random 0/1-polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-dimensional faces of random 0/1-polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120742