О случайных 2-смежностных 0/1-многогранниках

Оценивается вероятность $P_{k,m}$ того, что при случайном выборе $k$ вершин единичного куба $I_m=\{0,1\}^m$ их выпуклой оболочкой служит многогранник, граф которого является полным. Устанавливается, в частности, что вероятность $P_{k(m),m}$ стремится к единице, если $k(m)=O(2^{m/6})$, и $P_{k(m),m}$ стремится к нулю, если $k(m)\geq(3/2)^m$.
Результаты работы, во-первых, в значительной мере объясняют распространенность труднорешаемых дискретных задач и, во-вторых, подтверждают известную гипотезу Д. Гейла, опубликованную им в 1956 г.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 03–01–00822а.