Geodesic
On random 2-adjacent 0/1-polyhedra
Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 64-69.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2008_20_1_a4,
     author = {V. A. Bondarenko and A. G. Brodskiy},
     title = {On random 2-adjacent 0/1-polyhedra},
     journal = {Diskretnaya Matematika},
     pages = {64--69},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_1_a4/}
}
TY  - JOUR
AU  - V. A. Bondarenko
AU  - A. G. Brodskiy
TI  - On random 2-adjacent 0/1-polyhedra
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 64
EP  - 69
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_1_a4/
LA  - ru
ID  - DM_2008_20_1_a4
ER  - 
%0 Journal Article
%A V. A. Bondarenko
%A A. G. Brodskiy
%T On random 2-adjacent 0/1-polyhedra
%J Diskretnaya Matematika
%D 2008
%P 64-69
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_1_a4/
%G ru
%F DM_2008_20_1_a4
V. A. Bondarenko; A. G. Brodskiy. On random 2-adjacent 0/1-polyhedra. Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 64-69. http://geodesic.mathdoc.fr/item/DM_2008_20_1_a4/

[1] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, Moskva, 1981 | MR | Zbl

[2] Kristofides N., Teoriya grafov: Algoritmicheskii podkhod, Mir, Moskva, 1978 | MR

[3] Belov Yu. A., “O plotnosti grafa matroida”, Modeli issledovaniya operatsii v vychislitelnykh sistemakh, YarGU, Yaroslavl, 1985, 95–100

[4] Beloshevskii M. I., “Mnogogrannik zadachi o maksimalnom razreze”, Modeli i algoritmy matematicheskogo obespecheniya EVM, YarGU, Yaroslavl, 1986, 12–20

[5] Bondarenko V. A., “Sosednie vershiny mnogogrannikov, porozhdaemykh matroidami”, Voprosy teorii grupp i gomologicheskoi algebry, YarGU, Yaroslavl, 1982, 66–68 | MR

[6] Bondarenko V. A., “Nepolinomialnaya nizhnyaya otsenka slozhnosti zadachi kommivoyazhera v odnom klasse algoritmov”, Avtomatika i telemekhanika, 1983, no. 9, 45–50 | MR | Zbl

[7] Bondarenko V. A., Shunikova E. V., “Obobschennye perestanovochnye mnogogranniki i svoistva algoritmov sortirovki”, Modeli issledovaniya operatsii v vychislitelnykh sistemakh, YarGU, Yaroslavl, 1985, 105–113

[8] Bondarenko V. A., “Nepolinomialnye nizhnie otsenki slozhnosti optimizatsionnykh zadach o klike i vershinnom pokrytii v klasse pryamykh algoritmov”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, GGU, Gorkii, 1985, 59–65 | MR

[9] Bondarenko V. A., “Eksponentsialnost plotnosti grafa mnogogrannika zadachi o trekhmernom sochetanii”, Tezisy 7-i Vsesoyuznoi konferentsii “Problemy teoreticheskoi kibernetiki”, IGU, Irkutsk, 1985, 29

[10] Bondarenko V. A., “Otsenki slozhnosti zadach kombinatornoi optimizatsii v odnom klasse algoritmov”, Dokl. RAN, 328:1 (1993), 22–24 | MR | Zbl

[11] Bondarenko V. A., Poliedralnye grafy i slozhnost v kombinatornoi optimizatsii, YarGU, Yaroslavl, 1995

[12] Bondarenko V. A., “Poliedralnye grafy i slozhnost zadach kombinatornoi optimizatsii”, Matematika v Yaroslavskom universitete, YarGU, Yaroslavl, 1995, 31–42

[13] Greshnev S. N., “Mnogogrannik zadachi o $m$-vershinnom podgrafe polnogo grafa”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 24:5 (1984), 790–793 | MR | Zbl

[14] Maksimenko A. N., “Nizhnyaya otsenka plotnosti grafa mnogogrannika zadachi o parosochetaniyakh”, Sovremennye problemy matematiki i informatiki, 2001, no. 4, 157–161

[15] Maksimenko A. N., “Svodimost zadach diskretnoi optimizatsii i sootnoshenie plotnostei ikh poliedralnykh grafov”, Modelirovanie i analiz informatsionnykh sistem, 10:2 (2003), 3–10

[16] Maksimenko A. N., “Mnogogrannik zadachi o ryukzake”, Voprosy teorii grupp i gomologicheskoi algebry, YarGU, Yaroslavl, 2003, 163–172

[17] Maksimenko A. N., “Kombinatornye svoistva mnogogrannika zadachi o kratchaishem puti”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 44:9 (2004), 1693–1696 | MR | Zbl

[18] Barahona F., Mahjoub A. R., “On the cut polytope”, Math. Programming, 36 (1986), 157–173 | DOI | MR | Zbl

[19] Carathéodory C., “Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen”, Math. Ann., 64 (1907), 95–115 | DOI | MR | Zbl

[20] Geil D., “Sosednie vershiny na vypuklom mnogogrannike”, Lineinye neravenstva i smezhnye voprosy, IL, Moskva, 1959, 355–362

[21] Kaibel V., Remshagen A., “On the graph-density of random 0/1-polytopes”, Lect. Notes Computer Sci., 2764, 2003, 318–328 | MR

[22] Ziegler G. M., “Lectures on 0/1-polytopes”, Polytopes, Combinatorics and Computation, Birkhäuser, Basel, 2000, 1–41 | MR | Zbl