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

• Бродский, Алексей Германович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Бродский, Алексей Германович

Введение.

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 содержит, в частности, базовые результаты по двойственности Гейла и значимым при ее рассмотрении и применении свойствам систем точек. Эти базовые результаты изложены в виде лемм для удобства читателей и для удобства ссылок. Не все они являются но

Список литературы диссертационного исследования кандидат физико-математических наук Бродский, Алексей Германович, 2011 год

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.