On random 2-adjacent 0/1-polyhedra

V. A. Bondarenko ; A. G. Brodskiy

Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 64-69

Résumé

We estimate the probability $P_{k,m}$ that, as $k$ vertices of the unit cube $I_m=\{0,1\}^m$ are randomly chosen, their convex hull is a polyhedron whose graph is complete. In particular, we establish that, as $n\to\infty$, the probability $P_{k(m),m}$ tends to one if $k(m)=O(2^{m/6})$ and $P_{k(m),m}$ tends to zero if $k(m)\geq(3/2)^m$. The results given in this paper, first, to a great extent explain why the intractable discrete problems are so widely spread, and second, support the well-known Gale's hypothesis published in 1956.