ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2013, ТОМ 18, ВЫПУСК 2, СТР. 95-103

k-смежностные грани булева квадратичного многогранника

А. Н. Максименко

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

Булев квадратичный многогранник (или корреляционный многогранник) определяется как выпуклая оболочка

BQP(n) = conv{x = (xij) Î {0,1}n(n+1)/2 | xij = xiixjj, 1 £ i £ j £ n}.
Число 2n его вершин суперполиномиально по размерности d = n(n+1)/2. В 1992 г. М. Деза, М. Лоран и С. Поляк доказали, что BQP(n) 3-смежностный, т. е. любые три его вершины образуют грань этого многогранника. По аналогии с булевыми квадратичными многогранниками в статье рассматриваются булевы многогранники BQP(n,p) степени p. Для p = 2 BQP(n,p) совпадает с BQP(n). Для p = 1 BQP(n,p) -- n-мерный 0/1-куб. Показано, что BQP(n,p) s-смежностный при s £ p+ ëp/2û. Для m Î N и k ³ 2m доказано, что многогранник BQP(k,2m) линейно изоморфен некоторой грани многогранника BQP(n) при n = \Theta(\binom{k}{m}) $. Следовательно, для любого фиксированного s £ 3 ë(log2n)/2û BQP(n) имеет s-смежностную грань с суперполиномиальным числом $ 2^{\Theta ( n^{1 / \lceil s/3\rceil })} $ вершин.

Полнотекстовая версия статьи в формате PDF (160 Kb)

Главная страница Содержание журнала Новости Поиск

URL страницы: http://mech.math.msu.su/~fpm/rus/k13/k132/k13207h.htm
Изменения вносились 7 января 2014 г.