On random 2-adjacent 0/1-polyhedra
В. А. Бондаренко, Алексей Германович Бродский · Discrete Mathematics and Applications · 2008
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 → ∞, 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 ) ≥ (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.