О двойственности Гейла и смежностных случайных многогранниках тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

005004400

Бродский Алексей Германович

О ДВОЙСТВЕННОСТИ ГЕИЛА И СМЕЖНОСТНЫХ СЛУЧАЙНЫХ МНОГОГРАННИКАХ

01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

- 1 ДЕК 2011

Нижний Новгород — 2011

005004435

Работа выполнена на кафедре дискретного анализа Ярославского государственного университета им. П.Г. Демидова.

Научный руководитель:

доктор физико-математических наук, профессор Владимир Александрович Бондаренко

Официальные оппоненты:

доктор физико-математических наук, профессор

Валерий Николаевич Шевченко; доктор физико-математических наук, профессор Валерий Иванович Опойцев

Ведущая организация:

Институт проблем передачи информации им. А.А.Харкевича Российской академии наук

Защита диссертации состоится 15 декабря 2011 года в 14 часов 40 минут на заседании диссертационного совета Д 212.166.06 при Нижегородском государственном университете им. Н.И.Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, корп. 2, конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета им. Н.И.Лобачевского.

С текстом автореферата можно ознакомиться на сайте Нижегородского государственного университета им. Н.И. Лобачевского: http://www.unn.ru.

Автореферат разослан 4Ъка 2011 года.

Ученый секретарь диссертационного совета , , /1 ■ ^-И. Лукьянов

Общая характеристика работы

Актуальность темы

Исследования по теории выпуклых многогранников, тесно связанной с дискретной оптимизацией, проводились многими авторами (см., например, книги и статьи [4,1,2,5-7] и приведенную в них библиографию). Основные результаты диссертации находятся на стыке трех связанных между собой разделов этой теории: смежностные многогранники, двойственность Гейла, случайные многогранники.

Серьезный интерес к к-смсжпостным многогранникам [3] зародился более века назад после установления К. Каратеодори противоречащего геометрической интуиции факта существования к-смежностпых многогранников в

со сколь угодно большим числом вершин при <1 > 4 и к € 1, [с1/2\. Впоследствии смежностные многогранники неоднократно переоткрывались другими авторами, один из которых, Д. Гейл [22] предложил конструкцию, которая дает возможность по некоторым системам п точек на единичной {тп — 1)-мерной сфере С К"' (или сфере с присоединенным центром §т_! =

§т_1 и {0} С К'"), где п Зг то 4- 2, строить системы п точек из (в том числе являющиеся системами вершин /с-смсжностных многогранников), где (1 = п - гп - 1 и к £ 1, [(1/2\.

В частности, он обратил внимание на интуитивную ясность следующею утверждения1:

(0)1 вероятность получения /г-смежностного многогранника в результате применения конструкции Гейла к системе точек, выбранных из §т_1 наугад, быстро возрастает с увеличением <1.

В этой связи Д. Гейл высказал предположение о распространенности к-смежностных многогранников в многомерных пространствах и в качестве некоторого его уточнения выдвинул гипотезу, ставшую широко известной под названием «гипотеза Гейла»:

(в)А; вероятность получения /г-смежностного многогранника с п вершинами взятием выпуклой оболочки случайно выбранных п точек в Е"2 быстро возрастает с увеличением с/.

При к = 2 в формулировке гипотезы Гейла речь идет о 2-смежностных многогранниках, которые можно представлять как многогранники без диагоналей или как многогранники, граф которых является полным. Их связь с прикладными задачами впервые была осознана в результате развития теории сложности комбинаторных задач. Оказалось, что плотность графов многогран-

'Условимся называть его «вспомогательной гипотезой Гейла».

ников служит нижней границей временной трудоемкости алгоритмов из широкого класса, включающего большинство известных комбинаторных методов [26] (здесь под плотностью графа понимается максимальное количество попарно смежных вершин). Этим объясняется интерес к комбинаторным многогранникам с высокой плотностью графа. Оценки плотности полиэдральных графов большого количества комбинаторных задач показали, что эта величина экспоненциальна по размерности многогранников для труднорешаемых задач и полиномиальна для полиномиально разрешимых. При этом многогранники многих известных задач являются 2-смежностиыми.

Поскольку для ряда таких задач соответствующие многогранники являются 0/1 многогранниками (т.е. множества их вершин содержатся в множестве вершин стандартного единичного гиперкуба [0, ] ]''), естественно возник интерес к гипотезе Гейла для случайных 0/1 многогранников. Часть известных результатов подтверждает гипотезу Гейла для таких дискретных вероятностных моделей [1,23,25]. Исследовалась гипотеза Гейла и в непрерывном случае [10,9,30,11-13,27,14-18,21,25,8].

В дополнительных замечаниях и комментариях ко второму изданию книги [24, с. 129Ь] отмечается некорректность вопроса о вероятности fc-смежност-ности случайного многогранника, связанная с зависимостью от выбора модели случайного многогранника. В то же время существует сравнительно узкий круг известных утверждений о случайных системах точек, справедливых при очень слабых условиях на соответствующее распределение2. Мысль о том, что к числу таковых принадлежат и результаты, подтверждающие гипотезу Гейла и ее усиленные версии, была высказана Д.Л. Донохью и Д.Таннером в связи с обнаруженным ими фазовым переходом следующего вида [17,19,20]. Если А — случайная d х /¡-матрица, элементы которой независимы и распределены по нормальному закону ЛГ((), 1), и Р— вероятность /с-смежностности системы столбцов матрицы А, то существует пороговая функция а^т = &dt(p) такая, что для р > 1

р _ fl, если 0 < а < а от {(>), ,,

Jim Pd,LpdJ,L«rfJ п ^ / \ (1)

d^oo 10, если а > аот\Р)-

В обзоре [19], обсуждая итоги миллионов поставленных ими вычислительных экспериментов, Д.Л. Донохью и Д.Таннер формулируют гипотезу об универсальности этого фазового перехода (т.е. его справедливости для очень широкого, но пока неизвестного класса распределений).

Отметим, что дальнейшему усилению интереса к исследованию проблемы fc-смежностности случайного многогранника способствовало обнаружение ее

2Такне результаты принято называть «не зависящими от распределения» [28].

приложений к задаче нахождения самых разреженных решений неопределенных систем линейных уравнений и связанным с ней задачам цифровой обработки сигналов, теории кодирования, комбинаторной оптимизации и математической статистики.

Итак, актуальные исследования вопроса о /,>смежностности случайного многогранника, проводившиеся многими авторами, в диссертации продолжаются в направлении, указанном классическими и современными проблемами.

Цели работы

Основными целями работы являются нахождение оценок и асимптотического поведения вероятностей /с-смсжностпости или /с-космежностности случайных систем точек, подтверждение различных вариантов гипотез (0)1 и (О)к- Особое внимание уделяется утверждениям, справедливым при очень слабых условиях на распределение, важную роль в доказательствах которых играет двойственность Гейла. Поэтому двойственность Гейла становится еще одной сюжетной линией, развиваемой в диссертации.

Методы исследования

В работе использовались как классические методы исследования (двойственность Гейла, стандартная технология получения асимптотических формул и др.), так и новый метод, основанный на построенной автором двойственности для вероятностных пространств.

Научная новизна

Все основные результаты диссертации являются новыми. Это

1) теорема, дающая нижнюю оценку вероятности 2-смежностности выпуклой оболочки случайно выбранных без возвращения п вершин стандартного единичного гиперкуба (эта оценка используется для подтверждения гипотезы Гейла (С)2 для случайных многогранников указанной модели);

2) георема, дающая верхнюю и нижнюю оценки вероятности векторной к-смежиостиости случайной системы точек, подтверждающая гипотезу Гейла для широкого класса распределений;

3) теорема, дающая верхнюю и нижнюю оценки вероятности А.--космежнос-тности случайной системы точек, подтверждающая гипотезу (0)£ для широкого класса распределений;

4) теорема, дающая нижнюю оценку вероятности fc-космежностности системы п случайных точек, выбранных равномерно и независимо на сфере §т-Ь

5) теорема о двойственности вероятностных пространств специального вида.

Практическая и теоретическая ценность

Работа носит теоретический характер. Для широкого класса распределений получены результаты, подтверждающие гипотезу Гейла и ее усиленные версии. Развиваемая в диссертации техника может найти приложения в различных задачах теории выпуклых многогранников.

Личный вклад соискателя

Все включенные в диссертацию результаты, содержащие оценки и асимптотическое поведение вероятностей fc-смежностности или fc-космежностности случайных систем точек для произвольного к £ N (теоремы 2.1-2.3), получены автором лично. Для доказательства подтверждающей гипотезу Гейла и справедливой при очень слабых условиях на распределение теоремы 2.3 использована двойственность вероятностных пространств (теорема 1.1), также построенная самостоятельно. Оценка и асимптотическое поведение вероятности 2-смежностности случайного 0/1 многогранника (теорема 3.1) получены совместно с научным руководителем.

Апробация работы

Результаты диссертации докладывались на научной конференции студентов и аспирантов факультета информатики и вычислительной техники ЯрГУ 2006 года, на шестьдесят второй региональной научно-технической конференции студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь. Наука. Инновации — 2009» в г. Ярославле, на И Международной научно-практической конференции в г. Невинномысске, на VII молодежной научной школе по дискретной математике и ее приложениям в г. Москве.

Публикации

Результаты диссертации изложены в работах [33-39].

Структура и объем диссертации

Диссертация состоит из введения, трех глав и списка литературы. Текст диссертации изложен на 73 страницах (исключая список литературы). Список литературы содержит 74 названия.

Содержание работы

Все рассматриваемые многогранники предполагаются выпуклыми. Когда не оговаривается противное, всюду ниже d, т, п — натуральные числа, а к — целое неотрицательное число; кроме того, используются обозначения: JkJi — {р.р + 1,...,(]} — отрезок множества целых чисел (здесь p,<¡ £ Z и р ^ g); U2 = {—1)1} — группа квадратных корней из 1; X — непустое подмножество в К'г; Хп — множество всех систем п точек из X (в частном случае X = полагаем R'/,n = (К"1)"); Z — непустое подмножество в Wl'n\ LinConf(Z) — множество всех векторных конфигураций3 из Z; LinGeP(Z) — множество всех систем точек из Z, находящихся линейно в общем положении4; lina = linfai,. -., a„) — линейная оболочка системы точек а — (ai,... ,ап) е Kd'". Определим стандартно действие группы Uí,' на множестве Rd¡n, положив сra = (<ti«i ,... ,опап) для а = (ai,..., ап) € U^ и а — (ai,... ,ап) 6 Rd,n. Если в — отношение эквивалентности на множестве V и W — подмножество в V, то 0 индуцирует отношение эквивалентности на W, которое, допуская вольность обозначений, будем обозначать также через в. Для системы точек (ai,..., ап) £ под ее линейной зависимостью понимается точка (Ai,..., An) € R", являющаяся решением уравнения

а под аффинной зависимостью — точка (Ах,..., А„) £ К", являющаяся решением системы уравнений

Система точек а 6 Е'г,п называется к-смежиостной, если п ^ к + 1 и, кроме того, всякая ее ненулевая аффинная зависимость (А1,...,А„) € К"

3Векторными конфигурациями (в называются системы точек а £ имеющие

линейный ранг (I.

4Говорят, что точки системы а £ Е^™ находятся линейно в общем положении (в К4), если каждая ее тш(га, (¿)-компонентная подсистема линейно независима.

Aiai + ... + Апап = О,

{

Ai + ... + А„ = О, Ai ai + ... + Апап = 0.

имеет не менее к + 1 положительных компонент. Для к ^ 1 многогранник Р в К^ называется к-смежностпьш, если он имеет не менее к + 1 вершин и любое /с-элементное множество его вершин является множеством вершин некоторой грани многогранника Р. Систему точек а € й''"71 будем называть к-космежностной (в Ш1), если п ^ к + 1 и всякое открытое линейное полупространство5 в Е'г содержит хотя бы к + 1 точек системы а. Такие системы точек под различными названиями изучались многими авторами. Отметим роль, которую играют /с-смежностные и /. -космсжностные системы точек: для к > 1 система п точек из является /с-смежностной тогда и только тогда, когда ее выпуклая оболочка является /с-смежностным многогранником с п вершинами; /с-космежностность исходной системы точек является условием, необходимым и достаточным для получения /с-смежностной системы точек в результате применения конструкции Гейла.

Напомним, что дальнейшее развитие идей статьи [22] привело к созданию метода преобразований Гейла и диаграмм Гейла [24] и построению двойственности Гейла, ставших мощными инструментами для решения разнообразных задач комбинаторной теории многогранников. Нужная нам версия двойственности Гейла, которую будем называть векторной двойственностью Гейла, изложена в [32]. Она задается парой определяемых в предположении, что п = (1 + т, многозначных отображений: из 1лпСоп£(К'г,п) в ЬтСоп^К7"'71) и из ЫпСоп^К"1'") в ШСоп^'"). Для любой системы точек а = (аь.. .,а„) £ где сн = (а|,... ,а-г) С К* (1 < г < п), через Т,/,„(«) или, короче, Т(а) обозначим систему (а1,..., а'1) е 1п,(!, образованную точками ^ = (а{,...,а{) € К" (1 ^ з ^ &)■ В этих обозначениях, например, сопоставляет произвольной векторной конфигурации а £ ЫпСоп^К^'") множество всех ее векторных преобразований Гейла, т.е. таких векторных конфигураций Ь <5 1лпСопГ(Кт,п), для которых имеет место разложение К™ в ортогональную сумму М" = Ип Т(а) Фх Нп Т(Ь). Векторная двойственность Гейла позволяет некоторые свойства V векторной конфигурации из 1дпСоп£(К'г'") формулировать как векторио двойственные свойства V* = 'Р*'1" ее векторного преобразования Гейла, при этом имеем: V* — V. Приведем пример, важный для дальнейшего. Систему точек а Е будем называть векторно к-смежностиой, если п > к + 1 и всякая ее ненулевая линейная зависимость (Аг,..., А„) е К" имеет не менее к + 1 положительных компонент. Ясно, что векторно /с-смежносгная система точек о € Ег,'п является А;-смежностной. Обратное, вообще говоря, неверно. При любом к для век-

5Под открытым (замкнутым) линейным полупространством в К'' понимается открытое

(замкнутое) полупространство в ограниченное линейной гиперплоскостью в Ш.Л, т.е.

гиперплоскостью, проходящей через точку 0.

торных конфигураций «векторная /с-смежностность» и «/с-космежностность» являются свойствами, векторно двойственными друг другу.

Глава 1 диссертации содержит, в частности, базовые результаты по двойственности Гейла и значимым при ее рассмотрении и применении свойствам систем точек. Эти базовые результаты изложены в виде лемм для удобства читателей и для удобства ссылок. Не все они являются новыми. Во всех случаях, когда у автора была возможность сделать точную ссылку, известные (или близкие известным) результаты приводятся без доказательства.

С использованием двойственности Гейла в главе 1 строится двойственность для вероятностных пространств специального вида. Реализованная при этом идея по существу восходит к Д. Гейлу [22], считавшему возможным подходом к доказательству гипотезы (0)^ сведение к гипотезе (0)1. При этом Д. Гейл обращает внимание на необходимость уточнения требуемых для такого сведения вероятностных понятий, что фактически и делается с помощью построенной в диссертации двойственности вероятностных пространств. Для ее точного описания определим отношение эквивалентности Вт — 0'-\'п на множестве К'^", положив

а 0Г а' 37Ь ... ,7„ > 0 ПпТ(а') =

= {(71сь- • • ,7псп) ! (сь...,с„) е НпТ(а)}.

Подмножество X С К1' будем называть От-насьщенньш, если для всякого с 6 ЬшСопПЕ1''") найдется векторная конфигурация а £ ЫпСоп^Х"), для которой а вт с. В главе 1 устанавливается

Лемма 1.20. Пусть п = <1 + т. Если X и У являются вТ-насыщенными подмножествами в Ша и К"1 соответственно, то многозначные отображения vgt,^ п и п, задающие векторную двойственность Гейла, индуцируют взаимно обратные биекции

¥>,,,„ : ШСоЩХп)/вТ ^ ЬтСопИУ")/^ : (рт<п.

Вероятностное пространство У = (Г2, СВ,Р) будем называть абсолютно симметричным в том случае, если 1)52 С К^-" для некоторых й,п е М; 2) Ьш(ЗсР(П) е Ъ и Р(Ш(ЗеР(А)) = 1; 3) аВеЪи Р(<тВ) = Г(В) для любых (7 ё и'2' и В ё Ъ. Вероятностное пространство "Р — (П,23,Р) будем называть векторно гейловстш, если 1) О. = ЬшСоп^Х") для некоторых ¿,п € N (п > <1) и 0г-насыщенного подмножества X С К'г; 2) для любых В 6 23, Ь € В, а, € Л из а, вТ Ь следует, что а € В. С каждым таким пространством У и 0т-насыщенным подмножеством У С М"1, где тп — п — й, ассоциируем вероятностное пространство = (Л*,23*,Р*) такое, что 1) П* = ЬшСоп^У™);

2) Ъ* = {В* | В е Ъ}, где В* - ¥>d,n([6]r) (здесь через [&]г обозначен класс эквивалентности {a G Cl | а вт b}); 3) P*(J3*) = Р(В) для всех В е Ъ. Вероятностное пространство Уу будем называть Y-двойственным к векторно гейловскому вероятностному пространству У.

В главе 1 основной является объясняющая смысл построенной двойственности вероятностных пространств

Теорема 1.1. Пусть d,m € N; п = d + m; X и Y являются 0Г-насыщенными подмножествами в Md и Жт" соответственно; 1Р — векторно гейловское вероятностное пространство с пространством исходов LinConf(Xn). Тогда

1) вероятностное пространство Ту тоже является векторно гей-ловским;

2) если Y центрально симметрично (с центром в точке 0) и У абсолютно симметрично, то и Уу абсолютно симметрично;

3) = У.

В главу 2 включены леммы о борелевосги некоторых подмножеств в Е',,п, необходимые для обеспечения корректности получаемых далее оценок соответствующих вероятностей. При этом приводятся и доказательства необходимых «фольклорных» фактов, для которых диссертант не нашел доказательств в изученной литературе. Из трех теорем, являющихся основными результатами главы 2, первые две связаны с гипотезой (G)£.

Теорема 2.1. Пусть d,m,k £ N; к ^ [d/2J; п = d + rn и Prob*(d,n,k) — вероятность к-космежностности системы п случайных точек, выбранных независимо и равномерно на сфере §m_i. Тогда выполняется неравенство

Prob*(ri,п,к) >1-^-,

где

«<">-tGn)(rV -FI' ' =

В доказательстве теоремы 2.1 используется следующее наблюдение: любая открытая полусфера сферы §m_i содержит пересечение §m_i с некоторым открытым координатным ортантом пространства Ет.

Зафиксируем т,п е N, i е 1 ,п и подсистему I — (ii,...,it), в которой 1 ^ ¿1 < ... < it < п, системы чисел (1,2,... ,п). С каждой системой точек

а = (а:,..., «„,) е Ж7"'™ ассоциируем се подсистему а] = (а;,,..., а,;(). Кроме того, для подмножества Z С К"'-" условимся через обозначать мно-

жество всех систем точек а 6 2 таких, что а1 является О-космежностной системой точек из Кг">', а через ¥N¿(2) — множество всех систем точек а е '¿, для которых всякая ненулевая линейная зависимость (Аь...,А„) содержит хотя бы одну положительную компоненту А;, имеющую номер { е {¿1,... , Подмножество X С к'1 будем называть облачным, если оно имеет непустое пересечение с каждым открытым лучом {си | с > 0} (и £

Теорема 2.2, Пусть с1,т, к е М; Н 71 ~ <1+т; X — подмножество в К'"1 и У — абсолютно симметричное вероятностное пространство с пространством исходов X", удовлетворяющее условиюб:

(С) является событием для любой (п - к)-компонентной

подсистемы I системы чисел (1,2,..., п).

Тогда множество ОЧд^Х") всех к-космежностных систем точек а £ Хп является событием., для вероятности РгоЬ*(с1,п,к) которого имеют место утверждения:

1) выполняются неравенства

! _ 2-„+fc+i £ А» - k - 1\ ^ Prob*(dj П) к) ^

г=0

е'С"?"1

4 7 ¿=0 х

2) для любых р > 1 и а > гаах(0,2 — р)

РгоЬ*(сг, [р<1\, М) —> 0

при <1 -1- оо;

3) для любого р € (1,2) существует ао = а0(р) С (0, тш(1/2,2 - р)) такое, что для всякого а £ (0, «о)

Prob*(d, [pdj, [adj) —> 1

при d —> оо;

6Эю условие (£) выполнено, если ст-алгеброй событий является борелевская сх-алгебра в X71.

4) существует ах G (0,1/2) такое, что для любого фиксированного т и любого а £ (0, си)

Prob*(d,d, + m, [ad)) —> 1

при d ~> оо;

5) для фиксированного к

т. ,»/,1 ,1 , \ 11) есЛи 1 < Р < 2,

lim Prob (ii, [pd\,k) — %

10, если p > 2;

6) для фиксированных m и k

Prob* (d, d + rn, k) —> 1

при d -)• oo.

С целью доказательства теоремы 2.2 предварительно обосновывается лемма о точном значении вероятности О-космежностности случайной системы точек, являющаяся новой версией известной теоремы Венделя [31,29]. Обоснование леммы проводится аналогично рассуждению Венделя с дополнительным привлечением установленного в главе 1 с помощью двойственности Гей-ла факта: если п > d и существует замкнутое линейное полупространство в Kd, содержащее все точки системы а £ LiiiGeP(K<i,n), то существует' открытое линейное полупространство в R'', обладающее этим свойством.

Роль теорем 2.1 и 2.2. двоякая. Во-первых, утверждения 5) и 6) теоремы 2.2 подтверждают справедливость гипотезы (G)£ для произвольного k ^ 1 при некоторых способах согласованного роста параметров п и d, а утверждения 2)-4) содержат более сильные результаты. Отметим, что изучение вероятности Prob*(d, п, к) и гипотезы (СЩ представляет самостоятельный интерес, так как случайный выбор системы п точек в Sm_i, где n > т + 2, предназначенной для последующего применения конструкции Гейла, может рассматриваться как способ случайного порождения многогранника в Kn_m_1. В отличие от теоремы 2.1 теорема 2.2 является утверждением, справедливым при очень слабых условиях на распределение. Однако, например, при т = 1 оценка вероятности Prob*(rf, п, к) в теореме 2.1 сильнее ее нижней оценки в теореме 2.2. Иллюстрацией к теореме 2.1 служит такой числовой пример: случайно выбранные 19 точек на сфере So = {—1,1} образуют 2-космежностную систему точек (применение конструкции Гейла к которой дает 2-смежностный многогранник в Е17) с вероятностью, превышающей 0,999. Во-вторых, с использованием теоремы 2.2 и построенной двойственности вероятностных пространств (см. теорему 1.1) доказывается

Теорема 2.3. Пусть d,n,k € N; n > d; к < [d/2]; X - облачное подмножество в Rd и 'У — абсолютно симметричное вероятностное пространство с пространством исходов Хп, удовлетворяющее следующим двум условиям7:

(£) LinCoiif(X") является событием;

(<ДО1) VN/j(X") является событием для любой (п - к)-компонентной подсистемы I системы чисел (1,2,..., п).

Тогда множество VNfe(Xn) всех векторно к-смежностных систем точек а е Xй является событием, для вероятности Prob(d,n,k) которого имеют место утверждения 1)-6), получающиеся из утверждений 1)-6) теоремы 2.2 заменой Prob* на Prob.

Условия теоремы 2.3 выполнены в следующих трех важных частных случаях, позволяющих из теоремы 2.3 легко извлекать многочисленные следствия для конкретных распределений:

1) в множестве Rd выбираются тг случайных точек (н > d) независимо в соответствии с распределением, симметричным относительно точки 0 и абсолютно непрерывным относительно меры Лебега на R'1 (например, (¿-мерным нормальным распределением с нулевым вектором средних);

2) в множестве X = К, где К — центрально симметричное (с центром в точке 0) выпуклое тело в Rd (например, ¿-мерный единичный шар

выбираются п случайных точек (n > d) независимо в соответствии с распределением, симметричным относительно точки 0 и абсолютно непрерывным относительно меры Лебега на К (например, равномерным распределением на В,/);

3) в множестве X — OK, где дК — центрально симметричная (с центром в точке 0) выпуклая поверхность в Rfi (например, сфера Srf-i), выбираются п случайных точек (п > d) независимо в соответствии с распределением, симметричным относительно точки 0 и абсолютно непрерывным относительно поверхностной меры на дК (например, равномерным распределением на Sd-i).

Утверждения 5) и 6) теоремы 2.3 подтверждают справедливость гипотезы Гейла (G)/, для произвольного к > 1, а утверждения 2)-4) содержат более сильные результаты. Среди следствий, не известных ранее, — например, только что отмеченное утверждение о справедливости гипотезы Гейла для равномерных случайных многогранников на сфере §d-i-

7Эти условия (£) и (9391) выполнены, если <т-алгеброй событий является борелевская ст-алгебра в Хп.

В отличие от ранее известных подтверждений гипотезы Гейла и ее усиленных версий, обобщающая многие известные факты (см., например, [10,9]) теорема 2.3 является утверждением, справедливым при очень слабых условиях на распределение. Утверждения 2),3) теоремы 2.3 показывают, что в случае векторной /с-смежностности фазовый переход при линейно согласованном росте параметров п и с? имеет вид, отличный от случая А;-смежностности (см. (1)). В частности, в силу утверждения 2) порог отсутствует при р > 2.

Обозначим через РгоЬ0д((/,гг,2) вероятность того, что при случайном выборе без возвращения п вершин стандартного единичного гиперкуба --[0,1]^ их выпуклая оболочка является 2-смежностным многогранником (в терминологии из [23] речь идет о Р^л^-моде*т случайного 0/1 многогранника). Глава 3 посвящена изучению этой вероятности. Первым результатом в этом направлении стала нижняя оценка этой вероятности, полученная В.А. Бонда-ренко [1]. Основным результатом главы 3 является полученная В.А. Бондарен-ко и автором

Теорема 3.1. Если й, п е М; <1 ^ 2; п ^ 2'1 и РгоЬо/1(^, п,2) — вероятность 2-смежностности случайного 0/1 многогранника Р^А(пумодели, то

1) выполняется неравенство

РгоЬ0/1(сг,тг,2) >

п(п — 1)(п — 2)(тг — 3) 2 • — 11 • З'г + 14 • 2'1 - 5 ^ 8 (2Н — 1)(2'г — 2)(2'1 — 3) '

2) если п{д) = 0(2сЛ), где с — константа, удовлетворяющая неравенствам 0 < с < (3 — 1о^2 5)/4, то

РгоЬ0/1(й,п(<г),2) —1

при й -ч- 00.

Утверждение 1) теоремы 3.1 усиливает оценку из [1]. В качестве иллюстрации к нему приведем числовой пример: случайно выбранные без возвращения 25000 вершин 100-мерного гиперкуба образуют 2-смежностный многогранник с вероятностью, превышающей 0,999. Доказательство утверждения 1) использует достаточное условие 2-смежносгности 0/1 многогранника в терминах покомпонентных операций логического сложения и логического умножения на множестве {0,I}*1. Утверждение 2) подтверждает гипотезу Гейла

(G)o для случайных 0/1 многогранников Ргдл(п)-модсли. В этой связи отмстим следующее: поскольку с = 1/6 удовлетворяет условию теоремы 3.1, аналог ее утверждения 2) имеет место в предположении, что n(d) = 0(2d/b). Исследование вероятности fc-смежностности случайного 0/1 многогранника для произвольного к автором не проводилось в связи с появлением соответствующих результатов для равномерных случайных 0/1 многогранников в диссертации Р. Гиллмана [23] и статье Ш. Мендельсона, А. Пажора, Н. Томчак-Джагерманна [25] (в частности, подтверждающих справедливость при любом к > 1 гипотезы Гейла (G)/,., для равномерных случайных 0/1 многогранников).

Список литературы

[1] Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. — Ярославль: ЯрГУ, 1995. — 126 с.

[2] Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. — М.: Изд-во ЛКИ, 2008. — 184 с.

[3] БрёнстедА. Введение в теорию выпуклых многогранников. — М.: Мир, 1988.-240 с.

[4] Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). — М.: Наука, 1981. — 344 с.

[5] Шевченко В.Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. — 192 с.

[6] Шевченко В.Н. Триангуляции выпуклых многогранников и их булевы функции // Математические вопросы кибернетики. Вып. 16. — М.: Физматлит, 2007. - С. 43-56.

[7] Шевченко В.Н. Триангуляции выпуклых многогранников и реализация их /-векторов // Российская конференция «Дискретная оптимизация и исследование операций»: Материалы конференции (Алтай, 27 июня-3 июля 2010). — Новосибирск: Изд-во Ин-та математики, 2009. — С. 75-81.

[8] AdamczakR., LitvakA.E., PajorA., Tomczak-JaegermannN. Restricted isometry property of matrices with independent columns and neighborly poly-topes by random sampling. Preprint, 34 p., available at arXiv:0904.4723vl [math.PR] 30 Apr 2009.

[9] Bäränyl., Füredi Z. On the shape of the convex hull of random points // Probability Theory and Related Fields. - 1988. - V. 77, №2. - P. 231-240.

[10] BuchtaC. On a conjecture of R.E. Miles about the convex hull of random points // Monatshefte fur Mathematik. - 1986. - V. 102. - P. 91-102.

[11] CandesE., RudelsonM., TaoT., VershyninR. Error correction via linear programming // Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), IEEE. - 2005. - P. 295-308.

[12] CandesE., TaoT. Near optimal signal recovery from random projections and universal encoding strategies // IEEE Transactions on Information Theory. — 2004. - V. 52. - P. 5406-5425.

[13] CandesE., TaoT. Decoding by linear programming // IEEE Transactions on Information Theory. - 2005. - V. 51, №12. - P. 4203-4215.

[14] DonohoD.L. Neighborly polytopes and sparse solution of un-derdetermined linear equations. Preprint, 21 p., available at http://www-stat.Stanford.edu/~donoho/Reports/2005/ NPaSSULE-01-28-05.pdf.

[15] DonohoD.L. High-dimensional centrally-symmetric polytopes with neighbor-liness proportional to dimension // Discrete and Computational Geometry. — 2006. - V. 35, №4. - P. 617-652.

[16] DonohoD.L., Tanner J. Sparse nonnegative solution of underdetermined linear equations by linear programming // Proceedings of the National Academy of Sciences of the USA. - 2005. - V. 102, №27. - P. 9446-9451.

[17] DonohoD.L., Tanner J. Neighborliness of randomly-projected simplices in high dimensions // Proceedings of the National Academy of Sciences of the USA. - 2005. - V. 102, №27. - P. 9452-9457.

[18] DonohoD.L., Tanner J. Counting faces of randomly-projected polytopes when the projection radically lowers dimension // Journal of the American Mathematical Society. - 2009. - V. 22, №1. - P. 1-53.

[19] DonohoD.L., Tanner J. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing // Philosophical Transactions of the Royal Society. Ser. A. —

2009. - V. 367. - P. 4273-4293.

[20] Donoho D.L., Tanner J. Counting the faces of randomly-projected hypercubes and orthants, with applications // Discrete and Computational Geometry. —

2010. - V. 43, №3. - P. 522-541.

[21] DonohoD.L., Tanner J. Exponential bounds implying construction of compressed sensing matrices, error-correcting codes and neighborly polytopes by random sampling // IEEE Transactions on Information Theory. — 2010. — V. 56, №4. - P. 2002-2016.

[22] GaleD. Neighboring vertices on a convex polyhedron // Linear inequalities and related systems / H.W.Kuhn, A.W.Tucker, Eds. (Annals of Mathematics Studies. №38). — Princeton, New Jersey: Princeton University Press, 1956. — P. 255-263.

Имеется русский перевод: ГейлД. Соседние вершины на выпуклом многограннике // Линейные неравенства и смежные вопросы / Под ред. ГУ. Куна и А.У. Таккера. - М.: ИЛ, 1959. - С. 355-362.

[23] Gillmann R. 0/1-polytopes: typical and extremal properties. Dissertation. — Berlin: Technische Universität Berlin, 2007. — 125 p.

[24] Grünbaum B. Convex polytopes (Graduate Texts in Mathematics. V. 221). Second edition prepared by V. Kaibel, V. Klee and G.M. Ziegler. — New York: Springer, 2003. - 468 p.

[25] MendelsonS., PajorA., Tomczak-JaegermannN. Reconstruction and sub-gaussian operators in asymptotic geometric analysis // Geometric and Functional Analysis. - 2007. - V. 17, №4. - P. 1248-1282.

[26] MoravekJ. On the complexity of discrete programming problems // Aplikace Matematiky. - 1969. - V. 17, №6. - P. 442-^74.

[27] Rudelson M., Vershynin R. Geometric approach to error correcting codes and reconstruction of signals // International Mathematical Research Notices. — 2005. - V. 64. - P. 4019-4041.

[28] SchneiderR. Discrete aspects of stochastic geometry // Handbook of discrete and computational geometry / J.E. Goodman, J. O'Rourke, Eds. (second edition). - Boca Raton (Florida): Chapman & Hall / CRC Press, 2004. -P. 255-278.

[29] Sehneider R., WeilW. Stochastic and integral geometry (Probability and its Applications). — Berlin-Heidelberg: Springer, 2008. — 694 p.

[30] VershikA.M., Sporyshev P.V. Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem // Selecta Mathematica Sovietica. - 1992. - V. 11, №2. - P. 181-201.

[31] Wendel J.G. A problem in geometric probability // Mathematica Scandinav-ica. - 1962. - V. 11. - P. 109-111.

[32] Ziegler G.M. Lectures on polytopes (Graduate Texts in Mathematics. V. 152). — New York: Springer, 1995. — 370 p. (Updates, corrections, and more available at http://www.math.tu-berlin.de/~ziegler)

Публикации автора в изданиях, включенных в перечень ВАК РФ

[33] БондаренкоВ.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогранниках // Дискретная математика. — 2008. — Т. 20, №1. — С. 6469.

[34] Бродский А.Г. О 2-смежностных многогранниках и конструкции Гейла // Моделирование и анализ информационных систем. — 2009. — Т. 16, №2. — С. 5-21.

Другие публикации автора

[35] Бродский А.Г. О гипотезе Гейла и 2-смежностных многогранниках // Шестьдесят вторая региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь. Наука. Инновации — 2009». 15 апреля 2009 г., Ярославль: Тез. докл. - Ярославль: Изд-во ЯГТУ, 2009. - С. 203.

[36] Бродский А.Г. Вокруг гипотезы Гейла о 2-смежностных многогранниках // Молодежь и наука: реальность и будущее: Материалы И Международной научно-практической конференции (г. Невинномысск, 3 марта 2009) / Редкол.: В.А. Кузьмшцев, O.A. Мазур, Т.Н. Рябченко, A.A. Шатохин. T. VIII. - Невинномысск: НИЭУГ1, 2009. - С. 310-311.

[37] Бродский А.Г. О 2-смежностных мног огранниках // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18-23 мая 2009 г.). Часть I. / Под ред. A.B. Чашкина. - М.: ИПМ РАН, МГУ, 2009.-С. 10-14.

[38] Бродский А.Г. О двойственности Гейла и /с-смежностных случайных многогранниках // Заметки по информат ике и математике: сб. науч. ст. Вып. 2 / отв. ред. А.Н. Морозов; Яросл. гос. ун-т им. П.Г. Демидова. — Ярославль: ЯрГУ, 2010.-С. 28-33.

[39] Brodskiy A.G. On 2-neighborly polytopes and the Gale construction // Automatic Control and Computer Sciences. — 2010. - V. 44, №7. — P. 434-446.

Подписано в печать 27 октября 2011 г.

Формат 60x90/16

Объём 1,0 п.л.

Тираж 100 экз.

Заказ № 101111401

Оттиражировано на ризографе в ООО «УниверПринт»

ИНН/КПП 7728572912\772Х01001

Адрес: г, Москва, улица Ивана Бабушкина, д. 19/1.

Тел. 740-76-47,989-15-83.

hUp://www.univerprmt.ru

Введение.

1. О двойственности Гейла и двойственности вероятностных пространств.

2. О /с-космежностности и /с-смежностности случайной системы точек.

3. О 2-смежностности случайного

0/1 многогранника Р^а(п)-модели.

Исследования по теории выпуклых многогранников, тесно связанной с дискретной оптимизацией, проводились многими авторами (см., например, книги и статьи [16,3,6,20-22] и приведенную в них библиографию). Основные результаты диссертации находятся на стыке трех тесно связанных между собой разделов этой теории: смежностные многогранники, двойственность Гейла, случайные многогранники. Для каждого из них интенсивное развитие в последние десятилетия привело к трудной обозримости известных к настоящему моменту результатов и установлению связей с различными областями математики и приложениями.

Когда не оговаривается противное, всюду ниже с?, т, п — натуральные числа, а к — целое неотрицательное число; кроме того, используются обозначения: р, д = {р,р + 1,., д} — отрезок множества целых чисел (здесь р, д € Ъ и р ^ д); 112 = { — 1,1} — группа квадратных корней из 1; е \и\ ^ 1} и §¿-1 = {и £ | |и| = 1} — единичные шар и сфера в М^; §<¿-1 = и {0} — результат присоединения к сфере §£¿-1 точки 0 € X — непустое подмножество в Xй — множество всех систем п точек из X (в частном случае X — полагаем = (Мс/)п); 2 — непустое подмножество в Ш?'71; ЬтСоп£(^) и АЯСоп^/?) — множества всех векторных и всех точечных конфигураций из Z; ЫпСеР(^) и АЯСеР(^) — множества всех систем точек из Z, находящихся соответственно линейно в общем положении и аффинно в общем положении; Ип а = 1т(ах,., ап) и сош/ а = сопу(а1,., ап) — линейная и выпуклая оболочки системы точек а = (ах,., ап) £ М^™; а/ = (а^, а^,. ,а,ц) — I-подсистема системы точек а = (а\,. ,ап) £ М^'71 (здесь £ £ 1,п и I — (-¿1,. где 1 ^ г\ < . < ц ^ п, — подсистема системы чисел (1,2,. ,п)). Определим стандартно действие группы на множестве Мсг'п, положив ста = (стхах,., апап) для а = (стх,., ап) £ Щ и а = (ах,., ап) £ Если в — отношение эквивалентности на множестве V и\У — подмножество в V, то в индуцирует отношение эквивалентности на \¥, которое, допуская вольность обозначений, будем обозначать также через в.

Система точек а £ М^72, называется к-смежностной [46,48], если п^ к + 1 и всякая ее ненулевая аффинная зависимость (Ах,., Хп) £ Кп имеет не менее к + 1 положительных компонент. Для к ^ 1 выпуклый многогранник Р в М.а называется к-смежностным [8, 16,48,73], если он имеет не менее к + 1 вершин и любое /с-элементное множество его вершин является множеством вершин некоторой грани многогранника Р. Кроме того, [¿/2]-смежностные ¿-мерные многогранники называют просто смежностными. Известно [46], что для любого к ^ 1 система точек ах,., ап) € М^'71 является /с-смежностной тогда и только тогда, когда ее выпуклая оболочка сопу(ах,., ап) является /с-смежностным многогранником с множеством вершин {ах,., ап}.

В статье [45] Д. Гейл предложил конструкцию, позволяющую по некоторым векторным конфигурациям из 1лпСоп£(Хп), где X = §>тх и п ^ т + 2, строить точечные конфигурации (в том числе /с-смежностные) из АйСоп£ (К^'"), где (I = п-т-1 и к ^ [(1/2\. Систему точек а € Ша'п будем называть к-космежностной (в М^, если п ^ к + 1 и всякое открытое линейное полупространство в содержит хотя бы к + 1 точек системы а. Такие системы точек под различными названиями изучались многими авторами. Именно /с-космежностность исходной системы точек является условием, необходимым и достаточным для получения /с-смежностной системы точек в результате применения конструкции Гейла [48].

Дальнейшее развитие идей статьи [45] привело к созданию метода преобразований Гейла и диаграмм Гейла [48] и построению двойственности Гейла [73]. Нужная нам версия этой двойственности, которую будем называть векторной двойственностью Гейла, задается парой определяемых в предположении, что п = с1 + т, многозначных отображений: vgtdJn из ЫпСоп^М^) в 1лпСоп£(Кт'п) и vgtm)n из 1лпСоп£(Мт'п) в 1лпСоп£(Ксг,п). Условимся для системы точек а = (ах,., ап) € М^™, где аг = (аг-,.,а^) 6 М^ (1 ^ г < п), через Х^п(а) или, короче, Т{а) обозначать систему (а1,. ,ай) € Шп,(1, образованную точками а-7 = (а\,., а3п) е Кп (И ^ ^ с1). В этих обозначениях, например, vgtd)n сопоставляет каждой векторной конфигурации а е ЬтСоп^М^71) множество всех ее векторных преобразований Гейла, т.е. векторных конфигураций Ь € ЬтСоп^М771'™), для которых имеет место разложение Мп в ортогональную сумму Кп = Нп Т(а) НпТ(6). Векторная двойственность Гейла позволяет некоторые свойства V векторной конфигурации из ЬтСоМ(М^™) формулировать как векторно двойственные свойства V* = ее векторного преобразования Гейла, при этом имеем: V** = V. Приведем пример, важный для дальнейшего. Система точек а € М^" называется векторно к-смежностной [13], если п ^ к + 1 и всякая ее ненулевая линейная зависимость (Ах,., Ап) € Кп имеет не менее к + 1 положительных компонент. Ясно, что векторно /с-смежностная система точек а е является /с-смежностной. Обратное, вообще говоря, неверно. При любом к для векторных конфигураций «векторная /с-смежностность» и «/с-космежностность» являются свойствами, векторно двойственными друг другу (см. лемму 1.24).

В теории случайных многогранников, отраженной в книгах по геометрической вероятности, интегральной и стохастической геометрии (наиболее полно в [65]) и ряде обзоров (см. статьи [26,64,58] и приведенную в них библиографию), заметную роль играют исследования проблемы /с-смежностности случайного многогранника, в том числе связанные с известной гипотезой Гейла [45]. Прежде чем сформулировать ее, напомним об уже упоминавшейся конструкции Гейла, позволяющей для любого к € 1, [d/2\ по /с-космежностным системам п точек из 2, где п ^ d + 2, строить /с-смежностные многогранники с п вершинами из M.d. С точки зрения построения систем точек /с-космежностность оказалась более прозрачным и удобным условием по сравнению с к-смежностностью. В частности, Д. Гейл обратил внимание на интуитивную ясность следующего: для небольших значений к вероятность получения /с-космежностной системы при выборе точек из 2 наугад велика. В этой связи Д. Гейл [45] высказал предположение о распространенности Ar-смежностных многогранников в многомерных пространствах и в качестве некоторого его уточнения выдвинул гипотезу

G)k вероятность при случайном выборе точек а\,., ап в Md получить /с-смежностный многогранник conv(ai,., ап) с множеством вершин {ai,. ., ап} быстро возрастает с увеличением числа измерений d.

В том случае, когда речь идет о случайном выборе точек ai,. ,an из фиксированного подмножества X С Мс/, вместо гипотезы (G)/c будем говорить о гипотезе (G(X))fc.

Сам Д. Гейл указывал на необходимость дальнейших уточнений формулировки гипотезы (G)fc. Как правило, они включали в себя, во-первых, выбор конкретной модели случайного многогранника и, во-вторых, выбор способа согласованного роста п и d. Многочисленные известные результаты, подтверждающие гипотезу Гейла или ее аналог для случайных центрально симметричных многогранников [30,27,68,3,31-33,59,36-40, 43,47,57,25], относятся к различным моделям случайных многогранников и различным способам согласованного роста п и d: п = d + т, при фиксированном т € N, п = [pd\ для фиксированного р > 1 {линейно согласованный рост параметров d и п) и др. Линейно согласованный рост параметров впервые рассмотрели A.M. Вершик и П.В. Спорышев [68]. Для случайных многогранников предложенной ими модели они обнаружили явление резкого изменения комбинаторного строения многогранника при незначительном изменении р и исследовали соответствующую пороговую функцию ays = Oivs{p)- По существу A.M.Вершик и П.В. Спорышев установили для рассмотренных ими случайных многогранников более сильный по сравнению с оговоренным в гипотезе Гейла факт [ad\ -смеж-ностности1 для а < avs(p), имеющей место с высокой вероятностью при

Об этом факте говорят как о «смежностности, пропорциональной размерности» [37]. с? —>■ оо.

В дополнительных замечаниях и комментариях ко второму изданию книги [48, с. 129Ь] отмечается некорректность вопроса о вероятности к-смежностности случайного многогранника, связанная с зависимостью от выбора модели случайного многогранника. В то же время существует сравнительно узкий круг известных результатов о случайных системах точек, о каждом из которых говорят как о не зависящем от распределения — настолько слабы условия, накладываемые на соответствующее распределение [63]. Мысль о том, что к числу не зависящих от распределения принадлежат и результаты, подтверждающие гипотезу Гейла и ее усиленные версии, была высказана Д.Л. Донохью и Д. Таннером в связи с обнаруженным ими фазовым переходом следующего вида [39,41,42]. Если А — случайная ^ х п-матрица, элементы которой независимы и распределены по нормальному закону Л/"(0,1), и Р— вероятность к-смежностности системы столбцов матрицы А, то существует пороговая функция а от — &бт(р) такая, что для р > 1

В обзоре [41], обсуждая итоги миллионов поставленных ими вычислительных экспериментов, Д.Л. Донохью и Д. Таннер формулируют гипотезу об универсальности этого фазового перехода (т.е. его справедливости для очень широкого, но пока неизвестного класса матричных ансамблей).

В связи с гипотезой Гейла (О)¡с в [45] обсуждается гипотеза вероятность /с-космежностности случайной системы п точек из §>т1 быстро возрастает с увеличением п — т.

Большая часть основных результатов диссертации связана с подтверждением различных вариантов гипотез (в^ и {0)*к. Среди них — теоремы, содержащие оценки и асимптотическое поведение вероятностей к-космежностности или /с-смежностности случайных многогранников некоторых моделей. Особое внимание уделяется результатам, не зависящим от распределения, роль главного инструмента в доказательствах которых играет двойственность Гейла. Поэтому двойственность Гейла становится еще одной сюжетной линией, развиваемой в диссертации.

Текст диссертации изложен на 73 страницах (исключая список литературы). Список литературы содержит 74 названия. Диссертация состоит из введения и трех глав. Глава 1 содержит, в частности, базовые результаты по двойственности Гейла и значимым при ее рассмотрении и применении свойствам систем точек. Эти базовые результаты изложены в виде лемм для удобства читателей и для удобства ссылок. Не все они являются но

1. БогачевВ.И. Основы теории меры. Т. 1. -Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003. — 544 с.

2. БогачевВ.И. Основы теории меры. Т. 2. -Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003. — 576 с.

3. БондаренкоВ.А. Полиэдральные графы и сложность в комбинаторной оптимизации. — Ярославль: ЯрГУ, 1995. — 126 с.

4. БондаренкоВ.А., БродскийА.Г. О случайных 2-смежностных 0/1-многогранниках // Дискретная математика. — 2008. — Т. 20, №1. — С. 64-69.

5. БондаренкоВ.А., БродскийА.Г., МаксименкоА.Н. Плотность полиэдральных графов // Математика в Ярославском университете: Сборник обзорных статей. К 30-летию математического факультета / Отв. ред. В.Г. Дурнев. Ярославль, ЯрГУ, 2006. - С. 55-70.

6. БондаренкоВ.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. — М.: Изд-во ЛКИ,2008. 184 с.

7. Борисович Ю.Г., Гельман Б.Д., МышкисА.Д., ОбуховскийВ.В. Введение в теорию многозначных отображений и дифференциальных включений. — М.: КомКнига, 2005. — 216 с.

8. БрёнстедА. Введение в теорию выпуклых многогранников. — М.: Мир, 1988.-240 с.

9. Бродский А.Г. О 2-смежностных многогранниках и конструкции Гей-ла // Моделирование и анализ информационных систем. — 2009. — Т. 16, №2. С. 5-21.

10. Бродский А.Г. О 2-смежиостных многогранниках // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 18-23 мая 2009 г.). Часть I. / Под ред. А.В.Чашкина. М.: ИПМ РАН, МГУ, 2009. - С. 10-14.

11. Бродский А.Г. О двойственности Гейла и /с-смежностных случайных многогранниках // Заметки по информатике и математике: сб. науч. ст. Вып. 2 / отв. ред. А.Н.Морозов; Яросл. гос. ун-т им. П.Г.Демидова. — Ярославль: ЯрГУ, 2010. — С. 28-33.

12. Бродский А.Г., КалебинаМ.М. О случайных 2-смежностных 0/1-многогранниках // Научная конференция студентов и аспирантов факультета ИВТ 2006 года: тезисы докладов / Отв. ред. А.Н. Морозов; Яросл. гос. ун-т. — Ярославль: ЯрГУ, 2006. — С. 19-21.

13. Грэхем Р., Кнут Д., ПаташникО. Конкретная математика. Основание информатики. — М.: Мир, 1998. — 703 с.

14. ЕмеличевВ.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). — М.: Наука, 1981. 344 с.

15. РокафелларР. Выпуклый анализ. — М.: Мир, 1973. — 472 с.

16. СхрейверА. Теория линейного и целочисленного программирования. Т. 1. М.: Мир, 1991. - 360 с.

17. ХадвигерГ. Лекции об объеме, площади поверхности и изоперимет-рии. — М.: Наука, 1966. — 416 с.

18. Шевченко В.Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. — 192 с.

19. Шевченко В.Н. Триангуляции выпуклых многогранников и их булевы функции // Математические вопросы кибернетики. Вып. 16. — М.: Физматлит, 2007. С. 43-56.

20. Шилов Г.Е., ГуревичБ.Л. Интеграл, мера и производная (общая теория). М.: Наука, 1967. - 220 с.

21. ЭнгелькингР. Общая топология. — М.: Мир, 1986. — 752 с.

22. AdamczakR., LitvakA.E., PajorA., Tomczak-JaegermannN. Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Preprint, 34 p., available at arXiv:0904.4723vl math.PR] 30 Apr 2009.

23. Barany I. Random points and lattice points in convex bodies // Bulletin of the American Mathematical Society. 2008. - V. 45, №3. - P. 339365.

24. Barany I., FiirediZ. On the shape of the convex hull of random points // Probability Theory and Related Fields. 1988. - V. 77, №2. - P. 231240.

25. Barany I., PorA. On 0-1 polytopes with many facets // Advances in Mathematics. 2001. - V. 161, №2. - P. 209-228.

26. BrodskiyA.G. On 2-neighborly polytopes and the Gale construction // Automatic Control and Computer Sciences. — 2010. — V. 44, №7. — P. 434-446.

27. BuchtaC. On a conjecture of R.E. Miles about the convex hull of random points // Monatshefte fur Mathematik. 1986. - V. 102. - P. 91-102.

28. CandesE., RudelsonM., TaoT., VershyninR. Error correction via linear programming // Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), IEEE. 2005. -P. 295-308.

29. CandesE., TaoT. Near optimal signal recovery from random projections and universal encoding strategies // IEEE Transactions on Information Theory. 2004. - V. 52. - P. 5406-5425.

30. CandesE., TaoT. Decoding by linear programming // IEEE Transactions on Information Theory. 2005. - Y. 51, №12. - P. 4203-4215.

31. Davis C. Theory of positive linear dependence // American Journal of Mathematics. 1954. - V. 76. - P. 733-746.

32. DonohoD.L. Neighborly polytopes and sparse solution of un-derdetermined linear equations. Preprint, 21 p., available at http://www-stat.Stanford.edu/~donoho/Reports/ 2005/NPaSSULE-01-28-05.pdf.

33. DonohoD.L. High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension 11 Discrete and Computational Geometry. 2006. - V. 35, №4. - P. 617-652.

34. DonohoD.L., Tanner J. Sparse nonnegative solution of underdetermined linear equations by linear programming // Proceedings of the National Academy of Sciences of the USA. 2005. - V. 102, №27. - P. 94469451.

35. DonohoD.L., Tanner J. Neighborliness of randomly-projected simplices in high dimensions // Proceedings of the National Academy of Sciences of the USA. 2005. - V. 102, №27. - P. 9452-9457.

36. DonohoD.L., Tanner J. Counting faces of randomly-projected polytopes when the projection radically lowers dimension // Journal of the American Mathematical Society. 2009. - V. 22, №1. - P. 1-53.

37. DonohoD.L., Tanner J. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing // Philosophical Transactions of the Royal Society. Ser. A. 2009. - V. 367. - P. 4273-4293.

38. DonohoD.L., Tanner J. Counting the faces of randomly-projected hy-percubes and orthants, with applications // Discrete and Computational Geometry. 2010. - V. 43, №3. - P. 522-541.

39. DonohoD.L., Tanner J. Exponential bounds implying construction of compressed sensing matrices, error-correcting codes and neighborly polytopes by random sampling // IEEE Transactions on Information Theory. 2010. - V. 56, №4. - P. 2002-2016.

40. EwaldG. Combinatorial convexity and algebraic geometry (Graduate Texts in Mathematics. V. 168). New York: Springer, 1996. - 372 p.

41. Gale D. Neighborly and cyclic polytopes // American Mathematical Society Symposium on Convexity (Proceedings of Symposia in Pure Mathematics. V. 7). — Providence (R.I.): American Mathematical Society, 1963. P. 225-232.

42. GillmannR. 0/1-polytopes: typical and extremal properties. Dissertation. — Berlin: Technische Universität Berlin, 2007. — 125 p.

43. Grünbaum B. Convex polytopes (Graduate Texts in Mathematics. V. 221). Second edition prepared by V. Kaibel, V.Klee and G.M. Ziegler. New York: Springer, 2003. - 468 p.

44. HenkM., Richter-Gebert J., Ziegler G.M. Basic properties of convex polytopes // Handbook of discrete and computational geometry / J.E.Goodman, J.O'Rourke, Eds. (second edition). — Boca Raton (Florida): Chapman & Hall / CRC Press, 2004. P. 355-382.

45. Kaibel V. Low-dimensional faces of random 0/1-polytopes // Integer programming and combinatorial optimization (Lecture Notes in Computer Science. V. 3064). Berlin: Springer, 2004. - P. 401-415.

46. Kaibel V., Remshagen A. On the graph-density of random 0/1-polytopes // Approximation, randomization, and combinatorial optimization (Lecture Notes in Computer Science. V. 2764). — Berlin: Springer, 2003. P. 318-328.

47. Marcus D.A. Minimal positive 2-spanning sets of vectors // Proceedings of the American Mathematical Society. 1981. - V. 82, №2. - P. 165172.

48. Marcus D.A. Gale diagrams of convex polytopes and positive spanning sets of vectors // Discrete Applied Mathematics. — 1984. — V. 9. — P. 47-67.

49. McMullenP. Transforms, diagrams and representations // Contributions to Geometry. Proceedings of Geometry Symposium, Siegen 1978 / J.Tölke, J.Wills, Eds. Basel: Birkhaüser, 1979. - P. 92-130.

50. McMullenP, ShephardG.C. Diagrams for centrally symmetric poly-topes // Mathematika. 1968. - V. 15. - P. 123-138.

51. McMullenP., ShephardG.C. Convex polytopes and the Upper Bound Conjecture (London Mathematical Society Lecture Note Series 3). — Cambridge: Cambridge University Press, 1971. — 184 p.

52. MendelsonS., PajorA., Tomczak-JaegermannN. Reconstruction and subgaussian operators in asymptotic geometric analysis // Geometric and Functional Analysis. 2007. - V. 17, №4. - P. 1248-1282.

53. ReitznerM. Random polytopes // New perspectives in stochastic geometry / W.S.Kendall, I.Molchanov, Eds. — Oxford: Oxford University Press, 2010. P. 45-76.

54. RudelsonM., VershyninR. Geometric approach to error correcting codes and reconstruction of signals // International Mathematical Research Notices. 2005. - V. 64. - P. 4019-4041.

55. SanyalR., ZieglerG.M. Construction and analysis of projected deformed products // Discrete and Computational Geometry. — 2010. — V. 43, №2. P. 412^35.

56. Schneider R. Convex bodies: The Brunn-Minkowski theory (Encyclopedia of Mathematics and its Applications. V. 44). — Cambridge: Cambridge University Press, 1993. — 490 p.

57. Schneider R. Convex surfaces, curvature and surphace area measures // Handbook of convex geometry. V. A / P.M. Gruber, J.M. Wills, Eds. — Amsterdam: North-Holland, 1993. P. 273-299.

58. Schneider R. Discrete aspects of stochastic geometry // Handbook of discrete and computational geometry / J.E. Goodman, J. O'Rourke, Eds. (second edition). — Boca Raton (Florida): Chapman & Hall / CRC Press, 2004. P. 255-278.

59. Schneider R. Recent results on random polytopes // Bollettino dell'Unione Matematica Italiana. Sez. B. 2008. - V. 1. - P. 1739.

60. Schneider R., WeilW. Stochastic and integral geometry (Probability and its Applications). — Berlin-Heidelberg: Springer, 2008. — 694 p.

61. ShephardG.C. Diagrams for positive bases // Journal of the London Mathematical Society. 1971. - V. 4. - P. 165-175.

62. StoerJ., WitzgallC. Convexity and optimization in finite dimensions I (Grundlehren der mathematischen Wissenschaften. Band 163). — BerlinHeidelberg: Springer, 1970. 293 p.

63. VershikA.M., Sporyshev P.V. Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem // Selecta Mathematica Soviética. 1992. - V. 11, №2. - P. 181-201.

64. Wagner U. k-sets and /c-facets // Discrete and Computational Geometry — 20 Years Later / J.E.Goodman, J.Pach., R.Pollack, Eds. (Contemporary Mathematics. V. 453). Providence (R.I.): American Mathematical Society, 2008. P. 443-514.

65. Webster R. Convexity. — New York: Oxford University Press, 1994. — 444 p.

66. Wendel J.G. A problem in geometric probability // Mathematica Scandi-navica. 1962. - V. 11. - P. 109-111.

67. WotzlawR.F. Incidence graphs and unneighborly polytopes. PhD thesis. — Berlin: Technische Universität Berlin, 2009. — 216 p.

68. ZieglerG.M. Lectures on polytopes (Graduate Texts in Mathematics. V. 152). New York: Springer, 1995. - 370 p. (Updates, corrections, and more available at http://www.math.tu-berlin.de/ -ziegler) o

69. ZieglerG.M. Lectures on 0/1-polytopes // Polytopes — Combinatorics and Computation / G.Kalai, G.M.Ziegler, Eds. (DMV Seminars. V. 29). Basel: Birkhaüser, 2000. - P. 1-41.