|
This article is cited in 5 scientific papers (total in 5 papers)
On random 2-adjacent 0/1-polyhedra
V. A. Bondarenko, A. G. Brodskiy
Abstract:
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.
Received: 15.01.2006 Revised: 21.07.2006
Citation:
V. A. Bondarenko, A. G. Brodskiy, “On random 2-adjacent 0/1-polyhedra”, Diskr. Mat., 20:1 (2008), 64–69; Discrete Math. Appl., 18:2 (2008), 181–186
Linking options:
https://www.mathnet.ru/eng/dm989https://doi.org/10.4213/dm989 https://www.mathnet.ru/eng/dm/v20/i1/p64
|
Statistics & downloads: |
Abstract page: | 696 | Full-text PDF : | 294 | References: | 66 | First page: | 10 |
|