О свойствах полиэдральных комплексов и разбиений

Глазырин, Алексей Александрович

О свойствах полиэдральных комплексов и разбиений тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Глазырин, Алексей Александрович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2009 ГОД ЗАЩИТЫ

01.01.04 КОД ВАК РФ

Диссертация по математике на тему «О свойствах полиэдральных комплексов и разбиений»

Автореферат диссертации на тему "О свойствах полиэдральных комплексов и разбиений"

Московский государственный университет имени М.В. Ломоносова Механико-математический факультет

На правах рукописи УДК 514.124, 514.174.5, 514.172.45

Глазырин Алексей Александрович

О СВОЙСТВАХ ПОЛИЭДРАЛЬНЫХ КОМПЛЕКСОВ И

РАЗБИЕНИЙ

Специальность 01.01.04 — геометрия и топология

- 3 ДЕК 2009

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

Москва - 2009

003486010

Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

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

доктор физико-математических наук, профессор Николай Петрович Долбилин

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

доктор физико-математических наук Евгений Витальевич Щепин

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

Ярославский государственный университет им. П.Г. Демидова

Защита диссертации состоится 11 декабря 2009 г. в 16:45 на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 11 ноября 2009 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математические н^к-профессор

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

Общая характеристика работы Актуальность темы

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

В первой главе идет речь о развертках трехмерных евклидовых многогранников.

Определение развертки многогранника можно найти в книге А. Д. Александрова "Выпуклые многогранники"1. Фактически развертка многогранника — это совокупность плоских многоугольников с указанием правила склеивания их сторон так, что в результате склеивания получается поверхность многогранника.

Одна из наиболее замечательных теорем в теории выпуклых многогранников - теорема Александрова о единственности и существовании выпуклого многогранника с данной разверткой. Подчеркнем, что стороны многоугольников развертки выпуклого многогранника не обязаны быть ребрами этого единственного многогранника. Известно, что для каждого выпуклого многогранника найдется развертка, состоящая из одного (простого) многоугольника. Примеры таких разверток можно найти в работах2'3. В классе возможных разверток особый интерес представляют т.н. реберные развертки, т.е. развертки, в которых стороны многоугольников составлены из сторон многогранников.

Для данного многогранника Р существует лишь конечное число реберных разверток. Обозначим через С(Р) минимальное число компонент (многоугольников) у реберных разверток многогранника Р. Существует гипотеза, что для любого выпуклого многогранника Р С(Р) = 1. Эту гипотезу называют по имени великого художника Альбрехта Дюрера, в связи с тем что в его работах4 исследование многогранников сопровождалось реберными развертками, и эти развертки состояли из одной компоненты. Вопрос о С(Р) является одной из труднейших задач в теории многогранников5.

1А.Д. Александров. Выпуклые многогранники. М.-Л.: ГИТТЛ, 1950.

2В. Aronov, J. O'Rourke. Nonoverlap of the Star Unfolding. Disc. Comput. Geom. 8, 219-250, 1992.

SM. Sharir, A. Schorr. On shortest paths in polyhedral spaces, SIAM J. Comp. 15(1986), 193-215.

4A. Dürer. Underweysung der Messung mit dem Zirckel und Richtscheyt, bei Hieronymus Andrea«, Nürnberg 1525.

5G.C. Shephard. Convex polytopes with convex nets. Mathematical Proceedings of the Cambridge Philosophical Society, 78:389-403, 1975.

Отдельный интерес представляет задача нахождения верхней границы для С(Р) в зависимости от числа граней многогранника Р. Первая нетривиальная оценка вида kF (F - число граней многогранника Р, к < 1) была получена Сприггсом (Spriggs, 2003), который дал оценку для к —

Доминантным множеством называется такое множество М граней многогранника, что для любой грани либо сама эта грань, либо один из ее соседей находятся в множестве М. Несложно доказать, что минимальное число компонент развертки не больше минимальной мощности доминантного множества. На основе именно этой идеи и строятся наилучшие на текущий момент оценки. Астахов и Гаврилюк6 в своей работе показали, что доминантное множество состоит из не более чем граней. В. Пинчу7, сославшись на результат Б. Рида8 о доминантных множествах, получил оценку |F.

Существует несколько обобщений гипотезы Дюрера. Вот одно из таких обобщений:

Вопрос. Рассмотрим некоторый одномерный остов G на поверхности многогранника. Пусть этот остов делит поверхность на геодезические многоугольники, выпуклые в терминах внутренней метрики. Всегда ли существует однокомпонентная развертка многогранника, остовное дерево которой содержится в G?

В случае, когда все геодезические многоугольники являются треугольниками, этот вопрос был поставлен Дж. Эриксоном9.

Пример многогранника и одномерного остова на его поверхности, которые дают отрицательный ответ на поставленный выше вопрос, а также и на вопрос Эриксона, был дан А. Тарасовым10.

А. Тарасов11 также нашел пример невыпуклого многогранника с выпуклыми гранями, у которого нельзя найти реберной развертки, состоящей из одной компоненты.

еВ.В. Астахов, A.A. ГЪврилгок. О числе компонент в реберных развертках выпуклых многогранников. Модел. и анализ ииформ. систем. Т. 16, №1 (2009) 16-23.

7V. Pinciu. On the Fewest Nets Problem for Convex Polyhedra. CCCG 2007, Ottawa, Ontario, August 20-22, 2007.

eB.A. Reed. Paths, Stars and the Number Three, Comb. Probab. Comput., 5(1996), no. 3, 277-295.

9 J. Erickson. Oberwolfach-Conference "Discrete differential geometry", Problem 8, Berlin, March 2006.

10A. Tarasov. Existence of a polyhedron which does not have a non-overlapping pseudo-edge unfolding.

http://arxiv.org/abs/ 0806.2360, 2008.

nA.C. Тарасов. Многогранники, не допускающие натуральных разверток, "Успехи математических наук". Т. 54 выл 3 1999.

Берн и др.12 независимо нашли пример многогранника, у которого нельзя найти реберной развертки, состоящей из одной компоненты. Позднее Берном и др.13 был найден пример такого многогранника с дополнительным условием симплициальности (т.е. у этого примера все грани являются треугольниками).

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

Н. П. Долбилиным была поставлена задача доказать или опровергнуть т.н. Анти-Дюрер гипотезу15: sup С(Р) = оо для класса выпуклых многогранников. По его мнению, верна следующая альтернатива: для класса выпуклых многогранников sup С(Р) равен 1 или оо, т.е. верна либо гипотеза Дюрера, либо Анти-Дюрер гипотеза.

Мы покажем, что подобное утверждение верно для класса невыпуклых многогранников с выпуклыми гранями. То есть для любого N предъявим многогранник Р^ из этого класса, такой что С(Р^) > N.

Мотивацией для исследования во второй главе являются исследования в области квазипериодических подстановочных разбиений евклидова пространства на многогранники. Изучение квазипериодических структур - это бурно развивающаяся дисциплина на стыке геометрии, алгебры и анализа16-17-18'19-20-21.

13М. Bern, Е. D. Demaine, D. Epstein and Е. Kuo, Ununfoldable polyhedra. Proc. 11th Canad. Conf. on Comput. Geom. (CCCG'99), Vancouver, B.C., August 15 - 19.

"M. Bern, E. D. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Shoeyink. Ununfoldable polyhedra with convex faces. Computational Geometry: Theory and Applications, 24(2):51-62, February 2003.

UB. Grunbaum, No-net polyhedra. Geombmatorics 11(2002), 111 - 114.

15Н.П. Долбилин. Устное сообщение, ESI program "Rigidity and Flexibility", Vienna, April 23 - May 6,2006.

16D. Frettloh, E. Harriss. Tilings Encyclopedia, available online at: http: //tilings.math.uni-bielefeld.da.

17D. Frettloh. Duality of model sets generated by substitutions, Rev. Roumaine Math. Pures Appl. 50 (2005) 619-639; math.MG/0601064.

1SB. Solomyak. Dynamics of self-similar tilings, Ergodic Theory Dynam. Systems 17 (1997) 695-738. B. Solomyak. Corrections to 'Dynamics of self-similar tilings', Ergodic Theory Dynam. Systems 19 (1999) 1685.

"J. Kellendonk and I.F. Putnam. Tilings, C""-algebras and if-theory, in: Directions in Mathematical Quasicrystals, M. Baake and R.V. Moody (eds.), CRM Monograph Series, vol. 13, AMS, Providence, RI (2000) pp. 177-206.

20B. Solomyak. Non-periodicity implies unique composition property for self-similar translationally finite tilings, Discrete Comput. Geom. 20 (1998) 265-279.

21 J.-Y. Lee, R.V. Moody and B. Solomyak. Consequences of pure point diffraction spectra for multiset substitution systems, Discrete Comput. Geom. 29 (2003) 525-560.

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

Вопрос. Для локально конечного разбиения Т в пространстве R", все многогранники которого выпуклые, может ли существовать точка х, являющаяся вершиной ровно одного многогранника разбиения?

Другими словами, может ли быть в локально конечном полиэдральном разбиении "одинокая" вершина? Ответу на этот вопрос и связанным с ним задачам и посвящена вторая глава диссертации.

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

Первый вариант теоремы о четырех вершинах был получен Мухопа-дхаяей в 1909 году23. Позднее различные варианты этой теоремы были получены А. Кнезером, В. Бляшке24, Р. Бозе25. Возрастание интереса к этой проблеме в последние годы связано с работами В. И. Арнольда26,27. Несколько интересных результатов в этом же направлении было получено С. Табачниковым28,29.

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

"D. Prcttlöh. Nichtperiodische Pflasterungen mit ganzzahligem Inflationsfaktor, Ph.D. Thesis, Dortmund (2002); http://hdl.handle.net/2003/2309.

23S. MukUopadhayaya, New methods in the geometry of a plane arc -1, Cyclic and sextactic points, Bull. Calcutta Math. Soc., 1 (1909), 31-37.

24W. Blaschke, Kreis und Kugel, Leipzig: Veit, 1916

25R. С. Bose, On the number of circles of curvature perfectly enclosing or perfectly enclosed by a closed oval, Math. Ann., 35 (1932), 16-24.

26V. I. Arnold. Topological invariants of plane curves and caustics, Rutgers Univ. Lect. Series, Vol. 5, Amer. Math. Soc., Providence, 1994.

27B. И. Арнольд. Геометрия сферических кривых и алгебра кватернионов, УМН, 50:1, 1995, 3-68.

28С. Л. Табачников. Вокруг четырех вершин. УМН, 45, 1990, No 1, 229-230.

29S. Tabaclmikov. The Four-Vertex Theorem Revisited - Two Variations on the Old Theme, AMM, vol. 102, issue 10 (Dec. 1995), 912-916.

Различные дискретные варианты теоремы о четырех вершинах обсуждаются в работах О.Мусина30,31, Б.Вегнера32 и В. Д. Седых33.

Вариант теоремы о четырех вершинах для многогранников размерности больше двух был получен А. Шаттеманом34, который пытался доказать, что у каждого многогранника найдется по крайней мере 2d так называемых экстремальных сфер, где d - размерность многогранника. Однако, как мы покажем, рассуждения Шаттемана содержали ошибку, и, следовательно, вопрос о 2d экстремальных сферах остается открытым.

В 4 главе рассматриваются симплициальные разбиения и триангуляции. Под разбиением будем понимать представление многогранника в виде объединения неперекрывающихся, т.е. пересекающихся только по границе, многогранников. Мы будем рассматривать только симплициальные разбиения с вершинами симплексов в вершинах самого многогранника. В случае дополнительного условия, когда пересечение любых двух симплексов, если непусто, осуществляется по целой общей грани, разбиение является триангуляцией. Одной из важных задач, связанных с триангуляциями многогранников, является задача нахождения минимального числа симплексов в триангуляции данного многогранника.

Введем обозначения:

dis(n) - минимальное число симплексов в симплициальном разбиении n-мерного куба,

triang{n) - минимальное число симплексов в триангуляции п-мерного куба,

р(п) - максимальный определитель 0/1-матрицы.

Понятно, что triang(n) > dis(n). В работе все нижние оценки будут приведены для симплициальных разбиений. Следовательно, они будут также верны для триангуляций.

Очевидная оценка для dis(n) может быть получена с помощью евклидова объема:

»0. Р. Мусин. Системы Чебышева и нули функции на выпуклой кривой. Тр. МИАН, 221 (1998), 236-246.

3101eg R. Musin. Curvature extreina and four-vertex theorems for polygons and polyhedra, Journal of Mathematical Sciences, Vol. 119, Nо 2, 268-277, 2004.

32B. Wegner. Bose's vcrtex theorem for simply closed polygons, Math. Pannon., 6 (1995), 121-132.

33B. Д. Седых, Теорема о четырех опорных вершинах ломаной. Фунхцю анализ и его прил. 30, No 3 (1996), 88-90.

34А. Schatteman. А four-vertex theorem for polygons and its generalization to polytopes, Geometriae

Dedicata, 34 (1990), 229-242.

dis(n) > —— p(n)

Действительно, объем симплекса с вершинами в вершинах 0/1-куба не больше, чем и это автоматически дает приведенную выше оценку. Верхняя граница для р(п) следует из неравенства Адамара35:

Из этой оценки сразу же следует т.н. евклидова оценка на число симплексов в разбиении п-куба:

Более точные нижние оценки для сИз(п) могут быть получены, если вместо евклидова объема использовать другие объемы. Например, следующая оценка была доказана У. Д. Смитом36 с помощью гиперболического объема.

Необходимо также отметить некоторые работы37'38,39,40'41, посвященные минимальному числу симплексов в триангуляциях, симплициальных

^G. M. Ziegler. Lectures on 0/1-polytopes. Combinatorics and Computation, volume 29 of DMV Seminars, pages 1-41. Birkhauser-Verlag, Basel, 2000.

S6W.D Smith. A lower bound for simplexity of the n-cube via hyperbolic volumes. European J. Combin. 21(1} (2000), 131-137.

37R. W. Cottle. Minimal triangulation of the 4-cube. Discrete Math., 40(l):25-29, 1982.

38J. F. Sallee. A triangulation of the n-cube. Discrete Math., 40(1):81-в6, 1982.

39R. B. Hughes. Lower bounds on cube simplexity. Discrete Math., 133(1-3):123-138, 1994.

40R. B. Hughes and M. R. Anderson. Simplexity of the cube. Discrete Math., 158(l-3):99-150, 1996.

41A. Bliss, F. Б. Su. Lower bounds for simplicial covers and triangulations of. cubes, Discrete Comput. Geom. 33 (2005), 669-686.

dis(n)

dis(n) > H(n) > ~6?(n +

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

Цель работы

1. Исследовать аналог Анти-Дюрер гипотезы для класса невыпуклых многогранников с выпуклыми гранями.

2. Исследовать свойства ненормальных полиэдральных разбиений, в частности гипотезу об "одинокой" вершине

3. Получить .многомерный дискретный вариант теоремы о четырех вершинах.

4. Найти новую нижнюю асимптотическую оценку для числа симплексов в симплициальном разбиении п-мерного куба.

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

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

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

В третьей главе диссертации используются методы дискретной геометрии, общей топологии и линейной алгебры.

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

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

Основные результаты диссертации являются новыми и состоят в следующем:

1. Доказана Анти-Дюрер гипотеза для невыпуклых многогранников с выпуклыми гранями, то есть для любого натурального N построен многогранник Р^, реберная развертка которого состоит из по крайней мере N многоугольников.

2. Доказана теорема об "одинокой" вершине. Доказано также несколько обобщений этой теоремы. С помощью одного из этих обобщений получена теорема о невозможности существования конечной компоненты графа полиэдрального разбиения. Эта теорема позволяет доказать критерий того, что самоподобное подстановочное полиэдральное разбиение обладает конечной локальной сложностью.

3. Доказано многомерное обобщение дискретного варианта теоремы о четырех вершинах.

4. Доказана теорема об объемных инвариантах симплициальных разбиений призмоидов.

5. Найдена новая нижняя асимптотическая оценка на число симплексов в симплициальных разбиениях n-мерных кубов.

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

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

Апробация результатов

Основные результаты диссертации неоднократно докладывались на семинаре "Дискретная геометрия и геометрия чисел" под руководством Н.П. Долбилина и Н.Г. Мощевитина (мех-мат МГУ, 2006-2009); на семинаре им. М.М. Постникова "Алгебраическая топология и ее приложения" под руководством В.М. Бухштабера, A.B. Чернавского, И.А. Дынникова, JI.A. Алании, Д.В. Миллионщикова и Т.Е. Панова (мех-мат МГУ, 2007, 2009); на семинаре по геометрии им. И.Ф. Шарыгина (МЦНМО, 2007); на геометрическом семинаре ПОМИ РАН им. АД. Александрова под руководством ЮД. Бураго (ПОМИ РАН, 2009); на научно-исследовательском семинаре по теории чисел под руководством Ю.В. Нестеренко, Н.Г. Мощевитина (мех-мат МГУ, 2009); семинаре "Современные геометрические методы" под руководством А.Т. Фоменко, A.C. Мищенко, A.B. Болсинова, А.А Ошемкова, Е.А. Кудрявцевой (мех-мат МГУ, 2009), семинаре "Арифметика и геометрия" под руководством Н. Г. Мощевитина, А. М. Райгородского и О. Н. Германа (мех-мат МГУ, 2009), кафедральном семинаре кафедры дифференциальной геометрии и приложений под руководством А. Т. Фоменко (мех-мат МГУ, 2009).

Также результаты диссертации докладывались на следующих международных конференциях и семинарах: 2-nd СОЕ Workshop on Sphere Packings, Fukuoka, Japan (2005); ISM Symposium: Packing and random packing, Tokyo, Japan (2006); IX Международный семинар "Дискретная математика и ее приложения", посвященный 75-летию со дня рождения академика О.Б. Лупанова, Москва (2007); 10-th International Conference on Discrete Mathematics, Dortmund, Germany (2007); Mathematics research seminar, UTB, Brownsville, USA (2008); Combinatorics Seminar, CUNY, New York, USA (2008); Workshop on Combinatorial Geometry and Topology, South Padre Island, USA (2008); The 17th Annual Meeting of the South Texas Mathematics Consortium, Edinburg, USA (2009); The Discrete Geometry Workshop, South Padre Island, USA (2009); Русско-Японская конференция "Discrete Geometry and Statistics of Configurations", Москва (2009).

Публикации

Основные результаты диссертации опубликованы в шести работах, список которых приведен в конце автореферата [1-6].

Структура диссертации

Диссертация состоит из введения, четырех глав и списка литературы. Полный объем диссертации — 79 страниц, библиография включает 73 наименования.

Краткое содержание работы

Во введении дается обзор результатов, связанных с темой диссертации. Также формулируются основные результаты диссертации.

Первая глава посвящена разверткам многогранников. Основной результат главы составляет доказательство аналога Анти-Дюрер гипотезы для невыпуклых многогранников с выпуклыми гранями.

В разделе 1.1 приводятся основные определения, а также ставятся задачи, связанные с развертками многогранников. Основными гипотезами в этой области являются гипотеза Дюрера, впервые поставленная Шепардом, и Анти-Дюрер гипотеза, выдвинутая Н.П. Долбилиным. Помимо постановки задач в разделе также приводится доказательство того, что любой выпуклый многогранник с F гранями может быть развернут на не более чем у компонент и показано, почему требование выпуклости граней для Анти-Дюрер гипотезы является существенным, - приведен

простой пример, доказывающий Анти-Дюрер гипотезу для класса многогранников с невыпуклыми гранями.

В разделе 1.2 мы конструируем граф, в некотором смысле обобщающий знаменитый граф Татта42, явившийся контрпримером к гипотезе Тейта43 о гамильтоновсти реберных графов выпуклых многогранников. Построенный для заданного натурального N > 3 планарный трехсвяз-ный граф Tjv состоит из N так называемых фрагментов Татта.

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

В разделе доказывается следующее обобщение теоремы Татта:

Теорема 1.2.2. Для любого N > 3 в планарном трехсвязном графе Т^ число граней любого разрезания не менее у + §

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

В разделе 1.4 приводится собственно доказательство Анти-Дюрер гипотезы для невыпуклых многогранников с выпуклыми гранями. Пусть Qx выпуклый многогранник, реберный остов которого изоморфен графу TV- Такой многогранник существует по теореме Штейница. Построим у многогранника Qn на каждой простой (т.е. степени 3) вершине с суммой плоских углов больше 7Г по шипу. Пусть Q'n - полученный многогранник.

Теорема 1.4.1. Реберная развертка многогранника Q'N имеет больше j — 4 компонент.

Схема доказательства теоремы 1.4.1 следующая.

42 W.Т. Tutte. On Hamiltonian Circuits, J. London Math. Soc. 21, 98-101, 1946.

"P.G. Tait. Remarks on the Colouring of Maps. Proc. Royal Soc. Edinburgh 10, 729, 1880.

1. Для графа Т^ рассмотрим подграф Н, соответствующий развертке многогранника (¿'х.

2. Оценим число компонент развертки снизу через Т1 + Т2 — 5, где Т\ - число граней связного планарного графа Н, а 7г - число его висячих вершин.

3. Построим из графа Н разрезание Н' графа Гдг с числом граней, не превышающим Т\ + Т2. Воспользуемся обобщением теоремы Татта, доказанным в разделе 1.2. Число компонент развертки должны быть по крайней мере у + | — 5, тем самым теорема доказана.

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

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

Ключевой для доказательства теоремы об "одинокой" вершине является следующая теорема:

Теорема 2.2.1. Индикатор А-многогранника не может быть равен линейной комбинации с действительными коэффициентами индикаторов конечного числа В-многогранников.

Приведем здесь основные идеи доказательства этой теоремы. Доказательство будет проведено по индукции по размерности сферы. Для каждой сферической функции /:§"—> И и гиперплоскости И, проходящей через центр сферы, мы определяем верхний и нижний пределы этой функции по отношению к данной гиперплоскости - функции /д" : Б"-1 1 и Д" : В"-1 —> Е. Теперь предположим, что искомое линейное представление все же существует. Рассмотрим гиперплоскость И, проходящую через одну из граней данного А-многогранника. Рассмотрим верхний и нижний пределы этого линейного представления относительно гиперплоскости Ь и разность получившихся выражений. Как

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

Из этой теоремы следует сама теорема об "одинокой" вершине:

Теорема 2.2.5. Пусть Т — локально конечное разбиение Кп на выпуклые многогранники. Тогда не существует такой точки х € Шп, что х является вершиной ровно одного из многогранников разбиения Т.

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

Также в этом разделе доказано следствие из теоремы для граней больших размерностей.

Следствие 2.2.6. Каждая к-мерная грань какого-то многогранника в локально конечном разбиении Т пространства Кп на выпуклые многогранники покрыта конечным числом к-мерных граней других многогранников разбиения.

В разделе 2.3 доказано следующее обобщение теоремы об "одинокой" вершине:

Теорема 2.3.1. Пусть Т — локально конечное разбиение Ж" на выпуклые многогранники. Тогда не существует такой точки х € К" и (п — 1)-мерной гиперплоскости Н, проходящей через х, что х является вершиной ровно только многогранников Т, лежащих по одну и ту же сторону от Н и пересекающихся с Н только по х.

С помощью предыдущей теоремы мы доказываем, что граф разбиения не может иметь конечных компонент связности.

Теорема 2.3.2. Для локально конечного разбиения Т пространства Е" на выпуклые многогранники пусть О = (V, Е) будет следующий граф: V - это множество всех вершин многогранников разбиения Т. Вершины разных многогранников отождествлены, если они совпадают как элементы пространства К". Е - это множество ребер в такое, что (х, у) € Е тогда и только тогда, когда отрезок ху целиком составляет ребро какого-то из многогранников разбиения Т. Тогда все связные компоненты графа (7 бесконечны.

Раздел 2.4 посвящен подстановочным разбиениям. С помощью теоремы 2.3.2 доказывается следующий критерий того, что самоподобное подстановочное разбиение обладает конечной локальной сложностью (автором этого критерия является Д.Фреттлох, который для его доказательства и поставил вопрос об "одинокой" вершине).

Теорема 2.4.2. Пусть Т - самоподобное подстановочное разбиение с полиэдральными прототайлами и целым коэффициентом подобия. Без ограничения общности можем считать, что 0 - вершина любого из прототайлов. Если линейная оболочка над Ъ всех вершин прототай-лов образует дискретную решетку, то Т обладает конечной локальной сложностью.

В разделе 2.5 мы исследуем конфигурации, соответствующие вершинам разбиения, которые являются вершинами ровно двух многогранников разбиения (так называемым "двойным" вершинам) и доказываем для них следующую теорему.

Теорема 2.5.1. Пусть полиэдральное локально конечное разбиение единичной сферы Еп содержит ровно два А-многогранника Р, Р'. Пусть V — вершина Р. Тогда или V, или —и является вершиной Р'.

Третья глава посвящена многомерному дискретному варианту теоремы о четырех вершинах.

В разделе 3.1 приводятся различные варианты теоремы о четырех вершинах в гладком и дискретном случае. Также в этом разделе приведена гипотеза А. Шаттемана35, доказательство которой в статье самого Шаттемана, как мы покажем, неверно.

Рассмотрим выпуклый симплициальный многогранник Р в ¿-мерном евклидовом пространстве. Будем называть этот многогранник многогранником общего положения, если никакие его й + 2 вершины не лежат на одной сфере, и он не ¿-мерный симплекс. С этого момента мы будем рассматривать только многогранники общего положения. Каждая (д, — 2)-мерная грань однозначно определяет соседствующую сферу, проходящую через вершины двух фасет, пересекающихся по этой (в, — 2)-мерной грани. Соседствующая сфера называется пустой, если она не содержит других вершин Р, и она называется полной, если все остальные вершины Р находятся внутри нее. Мы будем называть пустые или полные соседствующие сферы экстремальными. Шаттеман сформулировал следующую теорему:

Теорема 3.1.5. Для каждого выпуклого d-мерного многогранника Р найдется по крайней мере d граней размерности d — 2, задающих пустые соседствующие сферы, и по крайней мере d граней размерности d — 2, задающих полные соседствующие сферы.

Раздел 2.2 посвящен доказательству двумерного дискретного случая.

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

Четвертый раздел главы посвящен тем идеям, которые использовал Шаттеман в своей попытке доказательства, однако для удобства мы будем использовать наши обозначения и определения.

Определение. Рассмотрим выпуклый симплициалъный многогранник общего положения Р и триангуляцию Делоне множества его вершин DT(P) (верхнюю триангуляцию Делоне UDT(P)). Мы будем называть симплекс S G DT(P) (S £ UDT(P)) D-ухом (UD-ухом), если по крайней мере две фасеты S лежат на границе многогранника Р.

В своей работе Шаттеман использует принцип расшелушиваемости (shellability). Давайте дадим формальное определение полиэдрального комплекса и его расшелушивания (shelling).

Определение. Полиэдральный комплексом С в Rd — это такой набор многогранников в Rd, что 1) пустое множество принадлежит С, 2) для любого многогранника Т £ С любая его грань Т также принадлежит С, 3) пересечение любых двух многогранников из С является гранью каждого из них.

Многогранники из набора, составляющего полиэдральный комплекс, также называются гранями комплекса. Размерностью комплекса С называют наибольшую размерность среди размерностей всех многогранников из С. Максимальные по включению грани комплекса называются фасетами комплекса. Если все фасеты комплекса имеют одну и ту же размерность, комплекс С называется чистым.

Теперь индуктивно определим понятие расшелушиваемости.

Определение. Каждый 0-мерный комплекс является расшелушивае-мым, его расшелушивание — это любой порядок его 0-мерных фасет.

Пусть теперь С — это чистый d-мерный полиэдральный комплекс. Будем называть С расшелушиваемым, если существует такой порядок (расшелушивание) его фасет (Fi, ... ,Fm), что Vs : 2 < s <

s-1

m; ((J Ft) f]Fs - это начало расшелушивания dFs. í=1

Если комплекс С - это ¿-клетка, то его расшелушивание (U F„) го-

t=1

меоморфно d-мерному диску для всех s (если это á-сфера, то последний гомеоморфен сфере).

Будем говорить, что фасета F многогранника Р видима из точки А, если А и Р находятся в разных полупространствах относительно гиперплоскости, проходящей через F. В классической работе Браггессера и Мани44 было доказано, что комплекс граней некоторого выпуклого многогранника, видимых из данной точки, является расшелушиваемым, а также дан метод построения расшелушивания. Просто соединяем данную точку с любой точкой внутри многогранника, и порядок, в котором получившаяся прямая пересекает гиперплоскости, проходящие через видимые фасеты (начиная изнутри многогранника), дает порядок многогранников в расшелушивании. Очевидно, что метод Браггессера и Мани можно применить для симплициального комплекса Делоне. Тем самым верна слудующая лемма.

Лемма 3.4.1. Симплицильный комплекс триангуляции Делоне (верхней триангуляции Делоне) расшелушиваем.

В своей статье Шаттеман доказал также следующую лемму (в работе мы приводим наше доказательство этого утверждения):

Лемма 3.4.2. Последний по порядку симплекс в расшелушивании комплекса Делоне (комплекса верхнего Делоне) является D-ухом (UD-ухом).

Определение. Последний симплекс любого расшелушивания комплекса DT(P) (UDT(P)), полученный посредством метода Браггессера и Мани для Р', называется BMD-ухом (BMUD-ухом).

В разделе 3.5 мы указываем на пробелы в доказательстве Шаттемана, а также приводим контрпример к одному из ключевых утверждений его доказательства.

■"Н. Bruggesser and P. Mani, Shellabie decompositions of cells and spheres, Math. Scand., 29 (1971), 197-205.

В разделе 3.6 с помощью леммы 3.4.2 мы доказываем две теоремы, которые являются обобщениями теоремы о четырех вершинах на многомерный случай.

Теорема 3.6.1. Для каждого выпуклого симплициалъного й-мерного многогранника общего положения Р найдутся по крайней мере два ВМВ-уха и по крайней мере два ВМ1Ю-уха.

Теорема 3.6.2. Для каждого выпуклого симплициалъного й-мерного многогранника общего положения Р найдутся по крайней мере <1 -Ь 1 ВМ-ушей (то есть суммарное число ВМБ-ушей и ВМиИ-ушей по крайней мере й + 1).

Стоит заметить, что доказанные нами факты не так сильны, как гипотеза Шаттемана, и, следовательно, она остается открытой.

Четвертая глава посвящена триангуляциям и симплициальным разбиениям выпуклых многогранников.

В разделе 4.1 мы вводим определения и показываем, почему интересующая пас задача нетривиальна.

В разделе 4.2 сделан обзор известных результатов, связанных с сим-плициальными разбиениями кубов.

В разделе 4.3 мы доказывает теорему об объемных инвариантах сим-плициальных разбиений призмоидов.

Пусть все вершины п-мерного многогранника Р € К" лежат в двух параллельных гиперплоскостях, т.е. Р является п-мерным призмоидом. Для определенности будем считать, что эти гиперплоскости задаются уравнениями х\ = 0 и х\ — Будем считать в = 1, так как это никак не влияет на все дальнейшие рассуждения. Пусть у нас также есть разбиение Д многогранника Р на п-мерные симплексы. Обозначим Дj = {Т е Д| ровно г вершин симплекса Т лежат в х\ — 0}. Обозначим через количество симплексов, лежащих в А,, через Т- - у-й симплекс множества Д*, а через У{Т?) - его п-мерный объем. Пусть для данного призмоида и его разбиения Д на симплексы У(г) обозначает суммарный объем симплексов из Д{.

Теорема 4.3.1. У(г) - функция, не зависящая от разбиения А, 1 <г < п.

Доказательство теоремы состоит из последовательного доказательства нескольких лемм.

Рассмотрим T¡ и его пересечение Mt с гиперплоскостью х\ = t, где

íe[o,i].

Лемма 4.3.2. (п - 1)-мерный объем S(Mt) = с?(1 - ьУ~Чп~1, где c¡ -некоторая константа, не зависящая от t.

Лемма 4.3.3. Для любого т € N многочлены Pi = í'(l — í)m_i, О < i < тп (базисные многочлены Бернштейна), линейно независимы.

Теперь рассмотрим какое-то разбиение Д многогранника Р на симплексы. Определим для него с*(Д) =

Лемма 4.3.4. c¿ не зависят от разбиения А и определяются только самим многогранником Р.

Из последней леммы теорема получается с помощью простого вычисления.

Используя те же методы, что и в доказательстве теоремы 4.3.1, мы доказываем следующий факт.

Следствие 4.3.5. Если выполгмются условия теоремы и S(t) = const, то V(i) ~ £V(P). Здесь S(t) — (n — 1)-мерный объем сечения Р гиперплоскостью Xi — t.

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

В разделе 4.5 изучаются симплициальные разбиения симплициальной призмы, и с помощью следствия 4.3.5 доказывается следующая теорема.

Теорема 4.5.1. Любое разбиение на симплексы симплициальной призмы размерности п содержит ровно п симплексов.

Шестой раздел главы целиком посвящен нижним оценкам на число симплексов в симплициальных разбиениях n-мерных кубов.

В первом подразделе этого раздела с помощью следствия 4.3.5 теоремы 4.3.1 мы строим общую конструкцию для нахождения нижних оценок

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

Во втором подразделе раздела 4.6 с помощью общей конструкции из предыдущего подраздела и специального выбора матрицы параметров, воспользовавшись неравенством Адамара, мы получаем новую нижнюю оценку, которая тем не менее все еще хуже, чем найденная Смитом36 оценка.

В третьем подразделе мы доказываем неравенство на детерминанты 0/1-матриц, с помощью которого при том же выборе матрицы параметров мы получаем оценку, которая экспоненциально улучшает результат Смита.

В последнем подразделе мы используем новую матрицу параметров и с помощью все того же неравенства на детерминанты получаем наилучшую асимптотическую оценку:

Теорема 4.6.6. Для всех натуральных п

Эта оценка дает очевидное асимптотическое улучшение по сравнению с евклидовой оценкой

где А - это константа экспоненциального улучшения, полученного Смитом.

«Мп) > (п + 1)^ =: ^з(п)

" = | = 1.359140914 > А = 1.261522510,

Благодарности

Автор выражает глубокую благодарность своему научному руководителю профессору Николаю Петровичу Долбилину за постановку задач, их обсуждение и многолетнюю поддержку. Автор также благодарен Алексею Тарасову, Арсению Акопяну, Олегу Мусину, Дирку Фреттлоху и Алексею Гарберу.

Публикации автора по теме диссертации

1. А. А. Глазырин, А. С. Тарасов. Анти-Дюрер гипотеза для невыпуклых многогранников. Успехи математических наук, 64(2009), номер 3, 179-180

2. A.A. Глазырин, О новом свойстве полиэдральных разбиений, Материалы IX Международного семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О. Б. Лупанова, 2007, стр. 377-379.

3. D. Frettloh, A. Glazyrin. The lonely vertex problem. Beitrage zur Algebra und Geometrie vol.50, No.l 2009, 71-79.

4. A.A. Глазырин. О симплициальных разбиениях многогранников. Математические заметки, 85(2009), номер б, 840-848.

5. A.A. Глазырин. Симплициальные разбиения кубов. Деп. в ВИНИТИ РАН 30.10.2009, №679-В2009, 15 с.

6. A.A. Глазырин. Многомерная теорема о четырех вершинах. Деп. в ВИНИТИ РАН 30.10.2009, №678-В2009, 15 с.

Подписано в печать 09. !(, О9 Формат 60x90 1/16. Усл. печ. л. Ц? Тираж/¿>¿7 экз. Заказ

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имениМ. В. Ломоносова

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Глазырин, Алексей Александрович

Введение

1 Развертки многогранников и гипотеза Дюрера

1.1 Развертки, основные результаты и гипотезы

1.2 Обобщение теоремы Татта.

1.3 Построение шипа и его свойства.

1.4 Доказательство основной теоремы.

2 Полиэдральные разбиения и теорема об "одинокой" вершине

2.1 Постановка задачи.

2.2 Теорема об "одинокой" вершине.

2.3 Применение теоремы об "одинокой" вершине.

2.4 Подстановочные разбиения.

2.5 "Двойная" вершина.

3 Многомерная теорема о четырех вершинах

3.1 Теорема о четырех вершинах.

3.2 Двумерный случай.

3.3 Построение разбиения Делоне с помощью поднятия на параболоид

3.4 Различные типы ушей и связь между ними.

3.5 Статус теоремы Шаттемана.

3.6 Теоремы о числе ушей.

4 Триангуляции куба

4.1 Триангуляции и симплициальные разбиения.

4.2 Обзор про триангуляции кубов.

4.3 Триангуляции призмоидов

4.4 Построение нерасширяемых множеств.

4.5 Разбиение симплициальной призмы.

4.6 Нижние оценки для числа симплексов в триангуляциях куба

4.6.1 Общая конструкция и задача линейного программирования

4.6.2 Первая асимптотическая оценка.

4.6.3 Вторая асимптотическая оценка.

4.6.4 Третья асимптотическая оценка.

Введение диссертация по математике, на тему "О свойствах полиэдральных комплексов и разбиений"

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

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

В первой главе идет речь о развертках трехмерных евклидовых многогранников.

Определение развертки многогранника можно найти в книге А. Д. Александрова "Выпуклые многогранники" [2]. Фактически развертка многогранника — это совокупность плоскР1Х многоугольников с указанием правила склеивания их сторон так, что в результате склеивания получается поверхность многогранника.

Одна из наиболее замечательных теорем в теории выпуклых многогранников - теорема Александрова о единственности и существовании выпуклого многогранника с данной разверткой. Подчеркнем, что стороны многоугольников развертки выпуклого многогранника не обязаны быть ребрами этого единственного многогранника. Известно, что для каждого выпуклого многогранника найдется развертка, состоящая из одного (простого) многоугольника. Примеры таких разверток можно найти в работах [22], [14]. В классе возможных разверток особый интерес представляют т.н. реберные развертки, т.е. развертки, в которых стороны многоугольников составлены из сторон многогранников.

Для данного многогранника Р существует лишь конечное число реберных разверток. Обозначим через С(Р) минимальное число компонент (многоугольников) у реберных разверток многогранника Р. Существует гипотеза, что для любого выпуклого многогранника Р С(Р) = 1. Эту гипотезу называют по имени великого художника Альбрехта Дюрера, в связи с тем что в его работах [4] исследование многогранников сопровождалось реберными развертками, и эти развертки состояли из одной компоненты. Вопрос о С(Р) является одной из труднейших задач в теории многогранников [16].

Доминантным множеством называется такое множество М граней многогранника, что для любой грани либо сама эта грань, либо один из ее соседей находятся в множестве М. Несложно доказать, что минимальное число компонент развертки не больше минимальной мощности доминантного множества. На основе именно этой идеи и строятся наилучшие на текущий момент оценки. Астахов и Гаврилюк [3] в своей работе показали, что доминантное множество состоит из не более чем граней. В. Пинчу [12], сославшись на результат Б. Рида [7] о доминантных множествах, получил оценку |F.

Существует несколько обобщений гипотезы Дюрера. Вот одно из таких обобщений:

В случае, когда все геодезические многоугольники являются треугольниками, этот вопрос был поставлен Дж. Эриксоном [6].

Пример многогранника и одномерного остова на его поверхности, которые дают отрицательный ответ на поставленный выше вопрос, а также и на вопрос Эриксона, был дан А. Тарасовым [9].

А. Тарасов [8] также нашел пример невыпуклого многогранника с выпуклыми гранями, у которого нельзя найти реберной развертки, состоящей из одной компоненты.

Берн и др. [20] независимо нашли пример многогранника, у которого нельзя найти реберной развертки, состоящей из одной компоненты. Позднее Берном и др. [21] был найден пример такого многогранника с дополнительным условием симплициальности (т.е. у этого примера все грани являются треугольниками).

Наиболее простой (минимальный по числу граней) пример принадлежит Бранко Грюнбауму [25]. Этот пример использует конструкцию шипов, придуманную Тарасовым.

Н. П. Долбилиным была поставлена задача доказать или опровергнуть т.н. Анти-Дюрер гипотезу [5]: sup С(Р) = оо для класса выпуклых многогранников. По его мнению, верна следующая альтернатива: для класса выпуклых многогранников sup С(Р) равен 1 или оо, т.е. верна либо гипотеза Дюрера, либо Анти-Дюрер гипотеза.

Мы покажем, что подобное Анти-Дюрер гипотезе утверждение верно для класса невыпуклых многогранников с выпуклыми гранями. То есть для любого N предъявим многогранник Р^ из этого класса, такой что C(Pn) > N.

Мотивацией для основной проблемы второй главы послужили подстановочные полиэдральные разбиения. Основная идея заключается в том, что есть конечное множество выпуклых многогранников - прототайлов Ti,.,Tm а также правило а, как увеличить каждый прототайл с одним и тем же коэффициентом подобия А, а потом разделить его на копир! — или в более общем случае заменить его копиями — изначальных прототайлов. Заметим, что подстановка cr отображает многогранники в конечные множества многогранников, конечные множества многогранников в (большие) конечные множества многогранников, а разбиения в разбиения. С помощью повторения подстановочного правила все большие и большие части пространства оказываются заполненными, давая в пределе разбиение всего пространства. Более точное определение подстановочного разбиения можно найти, например, в [29]. Обширный набор различных подстановочных разбиений и словарь связанных с ними терминов можно найти в [30].

Подстановочное правило для многогранников, если

XTi = (J Т (1 < % < ш)

Теа(Тг) где объединение не перекрывающееся) называется самоподобной подстановкой многогранников.

Следующее определение оказалось очень важным для теории непериодических разбиений. Оно помогает разобраться с некоторыми патологическими случаями и согласуется с другими понятиями из этой теории, например, пространством разбиений, или оболочкой разбиения [35], [32].

Определение. Пусть а - подстановка многогранников с прототайлами ,Тт. Множества ak(Ti) называются супертайлами (к-го порядка). Разбиение Т называется подстановочным разбиением (с подстановкой многогранников а), если для каждого конечного подмножества Т С Т найдутся такие г, к, что Т конгруэнтно подмножеству какого-то супертайла

Семейство всех подстановочных разбиений с соответствующей подстановкой а обозначается Ха.

Для многих результатов в теории подстановочных разбиений необходимым является условие конечной локальной сложности разбиения, см, например, [35], [36], [34].

Определение. Будем называть фрагментом разбиения Т совокупность всех ячеек Т, которые покрываются шаром некоторого радиуса.

Определение. Разбиение Т обладает конечной локальной сложностью (FLC), если для каждого г > 0 в Т найдется только конечное число различных с точностью до параллельного переноса фрагментов диаметра меньше г.

Обычно достаточно легко понять, обладает ли данное подстановочное разбиение конечной локальной сложностью. Например, любое разбиение грань-в-грань, т.е. такое, в котором пересечение любой пары многогранников является гранью каждого из них, с конечным числом прототайлов обладает конечной локальной сложностью. Часто для доказательства FLC используется более общее условие [28].

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

Для доказательства критерия конечной локальной сложности самоподобного подстановочного разбиения следующий вопрос был поставлен Дирком Фреттлохом в [28] как открытая проблема.

Вопрос. Для локально конечного разбиения Т в пространстве Мп; все многогранники которого выпуклые, моэ/сет ли существовать точка х, являющаяся вершиной ровно одного многогранника разбиения?

Другими словами, может ли быть в локально конечном полиэдральном разбиении "одинокая" вершина? Ответу на этот вопрос и связанным с ним задачам и посвящена вторая глава.

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

Первый вариант теоремы о четырех вершинах был получен Мухопадхаяей в 1909 году [43]. Позднее различные варианты этой теоремы были получены А. Кнезером, В. Бляшке [39], Р. Бозе [40]. Увеличение интереса к этой проблеме в последние годы связано с докладами и работами В. И. Арнольда (см [37, 38] и т.д.) Несколько интересных результатов в этом же направлении было получено С. Табачниковым ([51], [52]).

Дискретными аналогами теоремы о четырех вершинах являются лемма Коши, использованная им в 1813 г. в знаменитой работе о единственности многогранника с данными гранями, и лемма Александрова [2], использованная для доказательства единственности выпуклого многогранника с заданными нормалями и площадями граней.

Различные дискретные варианты теоремы о четырех вершинах обсуждаются в работах О.Мусина [45, 46], Б.Вегнера [55] и В. Д. Седых [50].

Вариант теоремы о четырех вершинах для многогранников размерности больше двух был получен А. Шаттеманом [49], который пытался доказать, что у каждого многогранника найдется по крайней мере 2d так называемых экстремальных сфер, где d - размерность многогранника. Однако, как мы покажем, рассуждения Шаттемана содержали ошибку, и, следовательно, вопрос о 2d экстремальных сферах остается открытым.

Мы будем использовать следующие обозначения: dis(n) - минимальное число симплексов в симплициальном разбиении n-мерного куба, triang(n) -минимальное число симплексов в триангуляции n-мерного куба, р(п) - максимальный определитель 0/1-матрицы. Понятно, что triang(n) > dis(n). В нашей работе все нижние оценки будут приведены для симплициальных разбиений. Следовательно, они будут также верны для триангуляций.

Очевидная оценка для dis(n) может быть получена с помощью евклидова объема: disin) > —г~с. р{п)

Действительно, объем симплекса с вершинами в вершинах 0/1-куба не больше, чем и это автоматически дает приведенную выше оценку. Верхняя граница для р(п) может быть получена с помощью некоторых матричных преобразований и неравенства Адамара (более подробно об этом можно прочитать, например, в [58]): у/п -f 14 ™+1

Лемма 4.2.1. р(п) < 2 f —-—

Мы получим это неравенство в качестве следствия одной из доказанных нами лемм.

Из данной оценки на определитель сразу же получаем оценку на число симплексов

Теорема 4.2.2. п] disin) > п+1- =: Е(п)

Более точные оценки могут быть получены, если вместо евклидова объема использовать другие объемы. Например, следующая оценка была доказана У. Смитом в работе [59] с помощью гиперболического объема. dis{n) > #(n) > lj-^n! lim (Ш) " = Л « 1.261522510 п-^оо \Е(п) )

Необходимо также отметить некоторые работы, посвященные минимальному числу симплексов в триангуляциях, симплициальных разбиениях или покрытиях n-мерного куба, в которых получены некоторые оценки на эти числа для конкретных значений размерности п - [62], [66], [64], [63], [61].

Основное содержание работы

Первая глава посвящена разверткам многогранников. Основной результат главы составляет доказательство гипотезы типа Анти-Дюрер для невыпуклых многогранников с выпуклыми гранями.

В разделе 1.1 приводятся основные определения, а также ставятся задачи, связанные с развертками многогранников. Основными гипотезами в этой области являются гипотеза Дюрера, впервые поставленная Шепардом, и Анти-Дюрер гипотеза, выдвинутая Н.П. Долбилиным. Помимо постановки задач в разделе также приводится доказательство того, что любой выпуклый многогранник с F гранями может быть развернут на не более чем j компонент и показано, почему требование выпуклости граней для Анти-Дюрер гипотезы является существенным, - приведен простой пример, доказывающий Анти-Дюрер гипотезу для класса многогранников с невыпуклыми гранями.

В разделе 1.2 мы конструируем граф, в некотором смысле обобщающий знаменитый граф Татта [11], явившийся контрпримером к гипотезе Тейта [10] о гамильтоновсти реберных графов выпуклых многогранников. Построенный для заданного натурального N > 3 планарный трехсвязный граф Хдг состоит из N так называемых фрагментов Татта.

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

В разделе доказывается следующее обобщение теоремы Татта:

Теорема 1.2.2. Для любого N > 3 в планарном трехсвязном графе Тм число граней любого разрезания не менее ~ + |

В третьем разделе главы мы приводим конструкцию шипа, введенную А. Тарасовым в 1999 г. [8] для построения примера неразворачиваемого в одну компоненту многогранника. Рассматривается простая вершина многогранника, от нее на ребрах многогранника откладываются равные и достаточно малые по длине отрезки. Тетраэдр с вершинами в четырех получившихся точках отрезается от многогранника, а к новой грани, появившейся после отрезания, пристраивается достаточно высокий тетраэдр, который и называется шипом. Для получившейся конструкции в этом разделе также доказывается пара локальных свойств разверток, которые будут использованы далее для доказательства основной теоремы главы.

В разделе 1.4 приводится собственно доказательство Анти-Дюрер гипотезы для невыпуклых многогранников с выпуклыми гранями. Пусть Qn выпуклый многогранник, реберный остов которого изоморфен графу Tjv- Такой многогранник существует по теореме Штейница [13]. Построим у многогранника Qn на каждой простой (т.е. степени 3) вершине с суммой плоских углов больше 7г по шипу. Пусть Q'N - полученный многогранник.

Теорема 1.4.1. Реберная развертка многогранника Q'N имеет больше ~ — 4 компонент.

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

В разделе 2.2 вводятся понятия сферических А- и В-многогранников. Мы называем выпуклый n-мерный сферический многогранник В-многогранни-ком, если он содержит два конца какого-нибудь диаметра сферы и Л-много-гранником в обратном случае.

Ключевой для доказательства теоремы об "одинокой" вершине является следующая теорема:

Теорема 2.2.1. Индикатор А-миогогранника не может быть равен линейной комбинации с действительными коэффициентами индикаторов конечного числа В-многогранников.

Из этой теоремы следует сама теорема об "одинокой" вершине:

Теорема 2.2.5. Пусть Т — локально конечное полиэдральное разбиение в Rn. Тогда не существует такой точки х G Мп; что х является вершиной ровно одного из многогранников разбиения Т.

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

Также в этом разделе доказано следствие из теоремы для граней больших размерностей.

Следствие 2.2.6. Каждая к-мерная грань какого-то многогранника в локально конечном полиэдральном разбиении Т пространства Мп покрыта конечным числом k-мерных граней других многогранников разбиения.

В разделе 2.3 доказано следующее обобщение теоремы об "одинокой" вершине:

Теорема 2.3.1. Пусть Т — локально конечное полиэдральное разбиение в Шп. Тогда не существует такой точки х Gtn и (п — 1)-мерной гиперплоскости Н, проходящей через х, что х является вершиной ровно только многогранников Т; лежащих по одну и ту эюе сторону от Н и пересекающихся с Н только по х.

С помощью предыдущей теоремы мы доказываем, что граф разбиения не может иметь конечных компонент связности.

Теорема 2.3.2. Для полиэдрального локально конечного разбиения Т пусть G = (V, Е) будет следующий граф: V - это множество всех вершин многогранников разбиения Т. Вершины отоэюдествлены, если они совпадают, как элементы пространства Mn. Е - это множество ребер в G, такое, что (х,у) £ Е тогда и только тогда, когда отрезок ху целиком составляет ребро какого-то из многогранников разбиения Т. Тогда все связные компоненты графа G бесконечны.

Теорема 2.4.2. Пусть Т - самоподобное подстановочное разбиение с полиэдральными прототайлами и целым коэффициентом подобия. Без ограничения общности можем считать, что 0 - вершина любого из прототайлов. Если линейная оболочка над Ъ всех вершин прототайлов образует дискретную решетку, то Т обладает конечной локальной сложностью.

Теорема 2.5.1. Пусть полиэдральное локально конечное разбиение единичной сферы содержит ровно два А-многогранника Р, Р'. Пусть v — вершина Р. Тогда или v, или —v является вершиной Р'.

Третья глава посвящена многомерному дискретному варианту теоремы о четырех вершинах.

В разделе 3.1 приводятся различные варианты теоремы о четырех вершинах в гладком и дискретном случае. Также в этом разделе приведена гипотеза А. Шаттемана, доказательство которой в статье самого Шаттемана, как мы покажем, неверно.

Рассмотрим выпуклый симплициальный многогранник Р в d-мерном евклидовом пространстве. Будем называть этот многогранник многогранником общего положения, если никакие его d + 2 вершины не лежат на одной сфере, и он не с£-мерный симплекс. С этого момента мы будем рассматривать только многогранники общего положения. Каждая (d — 2)-мерная грань однозначно определяет соседствующую сферу, проходящую через вершины двух фасет, пересекающихся по этой (d — 2)-мерной грани. Соседствующая сфера называется пустой, если она не содержит других вершин Р, и она называется полной, если все остальные вершины Р находятся внутри нее. Мы будем называть пустые или полные соседствующие сферы экстремальными. Шаттеман ([49], Theorem 2, р.232) сформулировал следующую теорему:

Раздел 2.2 посвящен доказательству двумерного дискретного случая. Вслед за Lectures on Discrete and Polyhedral Geometry И.Пака [47] будем называть сферу через три вершины многоугольника соседствующей, если эти вершины последовательны, разделенной, если среди этих вершин нет двух подряд идущих, и промежуточной в остальных случаях.

Теорема 3.2.1. Пусть Q Е R2 - выпуклый многогранник общего положения с п вершинами, где ть > 4. Обозначим за s^-, и и+ число полных окруснс-ностей, которые являются соседствующими, раздельными и промежуточными соответственно. Таким же образом обозначим за s,t- и число пустых окружностей, которые являются соседствующими, раздельными и промежуточными соответственно. Тогда s-j- — 1.1- ~ S— — t— — 2, s+ + t+ + и+ = + t- + U- = n — 2

Авторство теоремы в данном виде принадлежит О.Мусину. Однако стоит заметить, что схожие дискретные варианты уже прочно вошли в математический фольклор.

Четвертый раздел главы посвящен тем идеям, которые использовал Шат-теман в своей попытке доказательства, однако для удобства мы будем использовать наши обозначения и определения.

Определение. Рассмотрим выпуклый симплициальный многогранник общего положения Р и триангуляцию Делоне множества его вершин DT(P) (верхнюю триангуляцию Делоне UDT(P)). Мы будем называть симплекс S G DT(P) (S 6 UDT(P)) D-ухом (UD-ухом), если по крайней мере две фасеты S лежат на границе многогранника Р.

В своей работе Шаттеман использует принцип расшелушиваемости (shell-ability). Давайте дадим формальное определение полиэдрального комплекса и его расшелушивания (shelling, см также [56]).

Определение. Полиэдральный комплексом С eM.d — это такой набор многогранников в что 1) пустое множество принадлежит С, 2) для любого многогранника Т £ С любая его грань Т также принадлежит С, 3) пересечение любых двух многогранников из С является гранью каждого из них.

Теперь индуктивно определим понятие расшелушиваемости.

Определение. Каэюдый 0-мерный комплекс является расшелушиваемым, его расшелушивание — это любой порядок его 0-мерных фасет. Пусть теперь С — это чистый d-мерный полиэдральный комплекс. Будем называть С расшелушиваемым, если существует такой порядок (расшелушивание)

S-1 его фасет (Fi, F2,., Fm), что Vs : 2 < s < m; (1J Ft) f] Fs - это начало t=1 расшелушивания dFs. s

Если комплекс С - это (i-клетка, то его расшелушивание ((J Fs) гомеоt=1 морфно d-мерному диску для всех s (если это d-сфера, то последний гомео-морфен сфере).

Будем говорить, что фасета F многогранника Р видима из точки А, если А и Р находятся в разных полупространствах относительно гиперплоскости, проходящей через F. В классической работе Браггессера и Мани [41] было доказано, что комплекс граней некоторого выпуклого многогранника, видимых из данной точки, является расшелушиваемым, а также дан метод построения расшелушивания. Просто соединяем данную точку с любой точкой внутри многогранника, и порядок, в котором получившаяся прямая пересекает гиперплоскости, проходящие через видимые фасеты (начиная изнутри многогранника), дает порядок многогранников в расшелушивании. Очевидно, что метод Браггессера и Мани можно применить для симплициального комплекса Делоне. Тем самым верна следующая лемма.

Лемма 3.4.1 ([49], Lemma 1, р.237). Симплицильный комплекс триангуляции Делоне (верхней триангуляции Делоне) расшелушиваем.

Лемма 3.4.2 ([49], Lemma 2, р.237). Последний по порядку симплекс в расшелушивании комплекса Делоне (комплекса верхнего Делоне) является D-ухом (UD-ухом).

Определение. Последний симплекс любого расшелушивания комплекса DT(P) (UDT{P)), полученный посредством метода Браггессера и Мани для Р', называется BMD-ухом (ВMUD-ухом).

Теорема 3.6.1. Для каждого выпуклого симплициального d-мерного многогранника общего положения Р найдутся по крайней мере два BMD-yxa и по крайней мере два BMUD-yxa.

Теорема 3.6.2. Для каждого выпуклого симплициального d-мерного многогранника общего положения Р найдутся по крайней мере d + 1 ВМ-ушей (то есть суммарное число BMD-ушей и BMUD-ушей по крайней мере d+1).

Четвертая глава посвящена триангуляциям и симплициальным разбиениям выпуклых многогранников.

В разделе 4.1 мы вводим определения и показываем, почему интересующая нас задача нетривиальна.

В разделе 4.2 сделан обзор известных результатов, связанных с симплици-альньши разбиениями кубов.

В разделе 4.3 мы доказывает теорему об объемных инвариантах симпли-циальных разбиений призмоидов.

Пусть все вершины п-мерного многогранника Р G Шп лежат в двух параллельных гиперплоскостях, т.е. Р является n-мерным призмоидом. Для определенности будем считать, что эти гиперплоскости задаются уравнениями Х\ = 0 и х\ — s. Будем считать 5 = 1, так как это никак не влияет на все дальнейшие рассуждения. Пусть у нас также есть разбиение Д многогранника Р на п-мерные симплексы. Обозначим Д^ = {Т £ Д| ровно г вершин симплекса Т лежат в х\ = 0}. Обозначим через qi количество симплексов, лежащих в Дг-, через Т- - j-Vi симплекс множества Дг, а через V(T-) - его п-мерный объем. Пусть для данного призмоида и его разбиения Д на симплексы V(i) обозначает суммарный объем симплексов из Д*.

Теорема 4.3.1. У (г) - функция, не зависящая от разбиения А, 1 < г < п.

Доказательство теоремы состоит из последовательного доказательства нескольких лемм.

Рассмотрим Т- и его пересечение Mt с гиперплоскостью Х\ — t, где t € [0,1].

Лемма 4.3.2. (п — 1 )-мерный объем S{Mt) = с?(1 — 1)г~Нп~г, где с? - некоторая константа, не зависящая от t.

Лемма 4.3.3. Для любого т G N многочлены Pi = tl{ 1 — t)m~l, 0 < г < т (базисные многочлены Бернштейна [60]), линейно независимы.

Теперь рассмотрим какое-то разбиение Д многогранника Р на симплексы. Определим для него сг-(Д) = ^сЦА).

Лемма 4.3.4. q не зависят от разбиения Д и определяются только самим многогранником Р.

Из последней леммы теорема получается с помощью простого вычисления. Используя те же методы, что и в доказательстве теоремы 4.3.1, мы доказываем следующий факт.

Следствие 4.3.5. Если выполняются условия теоремы и S(t) = const, то V(i) = ~V(P). Здесь S(t) — (п — 1)-мерный объем сечения Р гиперплоскостью x\—t.

Теорема 4.5.1. Любое разбиение на симплексы симплициальной призмы размерности п содержит ровно п симплексов.

В первом подразделе этого раздела с помощью следствия 4.3.5 теоремы 4.3.1 мы строим общую конструкцию для нахождения нижних оценок - некоторый взвешенный объем симплекса, зависящий от матрицы параметров. В общем случае наилучшая оценка получается для матрицы, являющейся решением некоторой задачи линейного программирования, которая слишком сложна для решения уже в размерностях, начиная с семи, поскольку имеет очень много линейных ограничений.

Пусть L^J = d; kn = 0 для четных п и kn — 1 для нечетных п. Обозначим также vn — (d\)2d~kn ~ (|!)2. Во втором подразделе раздела 4.6 с помощью общей конструкции из предыдущего подраздела и специального выбора матрицы параметров, воспользовавшись неравенством Адамара, мы получаем следующую нижнюю оценку:

Теорема 4.6.2. что дает нам экспоненциальное улучшение евклидовой оценки, но все еще хуже, чем оценка, полученная Смитом с помощью гиперболических объемов.

В третьем подразделе мы доказываем неравенство на детерминанты 0/1-матриц, с помощью которого при все том же выборе матрицы параметров мы получаем следующую оценку:

Теорема 4.6.5. Для всех натуральных п > 4

Т =: ВД,

Hm ( ) = Hm n—>00 Y -fcsljl) J n—>00 \» nf 2~n

Hy/hii-b))», 1.2905389698 > 1.261522510

Последняя константа здесь - это константа экспоненциального улучшения из работы Смита по сравнению с евклидовой оценкой. Таким образом, найденная нами асимптотическая нижняя оценка на число симплексов в разбиении куба экспоненциально улучшает и результат Смита.

Теорема 4.6.6. Для всех натуральных п dis{n) > (п + l)1^ =: F3(n)

Эта оценка дает очевидное асимптотическое улучшение по сравнению с евклидовой оценкой 1 п п^ \" е lim { J" = Km ( —тгто^— ) = 7: = 1-359140914 п^оо \Е(п) J П^оо \П2(-)П) 2

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

1. А.Д. Александров. Внутренняя геометрия выпуклых поверхностей, ОГИЗ, Гостехиздат, М.-Л., 1948.

2. А.Д. Александров. Выпуклые многогранники. М.-Л.: ГИТТЛ, 1950.

3. В.В. Астахов, А.А. Гаврилюк. О числе компонент в реберных развертках выпуклых многогранников. Модел. и анализ информ. систем. Т. 16, №1 (2009) 16-23

4. Н.П. Долбилин. Устное сообщение, ESI program "Rigidity and Flexibility", Vienna, April 23 May 6, 2006.

5. J. Erickson. Oberwolfach-Conference "Discrete differential geometry", Problem 8, Berlin, March 2006.

6. B.A. Reed. Paths, Stars and the Number Three, Comb. Probab. Comput., 5(1996), no. 3, 277-295.

7. A.C. Тарасов. Многогранники, не допускающие натуральных разверток, "Успехи математических наук". Т. 54 вып 3 1999.

8. A. Tarasov. Existence of a polyhedron which does not have a non-overlapping pseudo-edge unfolding, http://arxiv.org/abs/ 0806.2360, 2008.

9. P.G. Tait. Remarks on the Colouring of Maps. Proc. Royal Soc. Edinburgh 10, 729, 1880.

10. W.T. Tutte. On Hamiltonian Circuits, J. London Math. Soc. 21, 98-101, 1946.

11. V. Pinciu. On the Fewest Nets Problem for Convex Polyhedra. CCCG 2007, Ottawa, Ontario, August 20-22, 2007.

12. E. Steinitz, H. Rademacher. Vorlesungen liber die Theorie der Polyeder, Springer, Berlin, 1934.

13. M. Sharir, A. Schorr. On shortest paths in polyhedral spaces, SIAM J. Сотр. 15(1986), 193-215.

14. Ю.А. Волков и Е.Г. Подгорная. Множество раздела полиэдральной поверхности положительной кривизны, Укр. Геом. Сб. 11 (1971), 15-25.

15. G.C. Shephard. Convex polytopes with convex nets. Mathematical Proceedings of the Cambridge Philosophical Society, 78:389-403, 1975.

16. C. Schevon. Unfolding polyhedra. (A sci.math article, see http://www.ics.uci.edu/ eppstein/gina/unfold.html), February 1987.

17. C. Schevon. Algorithms for Geodesies on Polytopes. PhD thesis, Johns Hopkins Univ., 1989.

18. J. O'Rourke. Folding and unfolding in computational geometry. In Revised Papers from the Japan Conference on Discrete and Computational Geometry, volume 1763 of Lecture Notes in Computer Science, pages 258266, Tokyo, Japan, December 1998.

19. M. Bern, E. D. Demaine, D. Epstein and E. Kuo, Ununfoldable polyhedra. Proc. 11th Canad. Conf. on Comput. Geom. (CCCG'99), Vancouver, B.C., August 15 19.

20. M. Bern, E. D. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Shoeyink. Ununfoldable polyhedra with convex faces. Computational Geometry: Theory and Applications, 24(2):51-62, February 2003.

21. B. Aronov, J. O'Rourke. Nonoverlap of the Star Unfolding. Disc. Comput. Geom. 8, 219-250, 1992.

22. B. Griinbaum, Nets of polyhedra II. Geombinatorics Vol. 1, No. 3 (1991), 5 10.

23. B. Griinbaum, A starshaped polyhedron with no net. Geombinatorics 11(2001), 43-48.

24. B. Griinbaum, No-net polyhedra. Geombinatorics 11(2002), 111 114.

25. L. Danzer. Inflation species of planar tilings which are not of locally finite complexity, Proc. Steklov Inst. Math. 239 (2002) 118-126.

26. N.P. Prank, E.A. Robinson, Jr. Generalized beta-expansions, substitution tilings, and local finiteness, to appear in Trans. Amer. Math. Soc.

27. D. Frettloh. Nichtperiodische Pflasterungen mit ganzzahligem Inflationsfaktor, Ph.D. Thesis, Dortmund (2002); http://hdl.handle.net/2003/2309.

28. D. Frettloh. Duality of model sets generated by substitutions, Rev. Roumaine Math. Pures Appl. 50 (2005) 619-639; math.MG/0601064.

29. D. Frettloh, E. Harriss. Tilings Encyclopedia, available online at: http://tilings.math.uni-bielefeld.de.

30. B. Grtinbaum, G.C. Shephard. Tilings and Patterns, Freeman, New York (1987).

31. J. Kellendonk and I.F. Putnam. Tilings, C*-algebras and if-theory, in: Directions in Mathematical Quasicrystals, M. Baake and R.V. Moody (eds.), CRM Monograph Series, vol. 13, AMS, Providence, RI (2000) pp. 177-206.

32. J. C. Lagarias. The impact of aperiodic order on mathematics, Materials Science & Engineering A, 294-296 (2000) 186-191.

33. J.-Y. Lee, R.V. Moody and B. Solomyak. Consequences of pure point diffraction spectra for multiset substitution systems, Discrete Comput. Geom. 29 (2003) 525-560.

34. B. Solomyak. Dynamics of self-similar tilings, Ergodic Theory Dynam. Systems 17 (1997) 695-738.B. Solomyak. Corrections to 'Dynamics of self-similar tilings', Ergodic Theory Dynam. Systems 19 (1999) 1685.

35. B. Solomyak. Non-periodicity implies unique composition property for self-similar translationally finite tilings, Discrete Comput. Geom. 20 (1998) 265279.

36. V. I. Arnold. Topological invariants of plane curves and caustics, Rutgers Univ. Lect. Series, Vol. 5, Amer. Math. Soc., Providence, 1994.

37. В. И. Арнольд. Геометрия сферических кривых и алгебра кватернионов, УМН, 50:1, 1995, 3-68.

38. W. Blaschke, Kreis und Kugel, Leipzig: Veit, 1916.

39. R. C. Bose, On the number of circles of curvature perfectly enclosing or perfectly enclosed by a closed oval, Math. Ann., 35 (1932), 16-24.

40. H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand., 29 (1971), 197-205.

41. B. N. Delaunay. Sur la sphere vide. A la memorie de Georges Voronoi, О простом шаре. Известия Акад. наук СССР, отд. мат. и естеств. наук, 6 (1934), 793-800.

42. S. Mukhopadhayaya, New methods in the geometry of a plane arc -1, Cyclic and sextactic points, Bull. Calcutta Math. Soc., 1 (1909), 31-37.

43. О. P. Мусин. О четырех вершинах для многоугольника. Квант, №2,1997, 11-13.

44. О. Р. Мусин. Системы Чебышева и нули функции на выпуклой кривой. Тр. МИАН, 221 (1998), 236-246.

45. О. R. Musin. Curvature extrema and four-vertex theorems for polygons and polyhedra, Journal of Mathematical Sciences, Vol. 119, No 2, 268-277, 2004.

46. I. Pak. Lectures on Discrete and Polyhedral Geometry, http://www.math.umn. edu/pak/book.htm

47. M. E. Rudin. An unshellable triangulation of a tetrahedron, Bull. Amer. Math. Soc., 64 (1958), 90-91.

48. A. Schatteman. A four-vertex theorem for polygons and its generalization to polytopes, Geometriae Dedicata, 34 (1990), 229-242.

49. В. Д. Седых. Теорема о четырех опорных вершинах ломаной. Функцю анализ и его прил. 30, No 3 (1996), 88-90.

50. С. JI. Табачников. Вокруг четырех вершин. УМН, 45, 1990, No 1, 229230.

51. S. Tabachnikov. The Four-Vertex Theorem Revisited Two Variations on the Old Theme, AMM, vol. 102, issue 10 (Dec. 1995), 912-916.

52. M. Umehara. A unified approach to the four vertex theorems. I, Amer. Math. Soc. Transl., Ser. 2, 190 (1999), 185-228.

53. G. F. Voronoi. Nouvelles applications des parametres continus a la theorie des formes quadratiques, J. Reine Angew. Math., 34 (1908), 198-287.

54. B. Wegner. Bose's vertex theorem for simply closed polygons, Math. Pannon., 6 (1995), 121-132.

55. G. M. Ziegler. Lectures on polytopes, vol. 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, (1995).

56. J.A. De Loera. Computing minimal and maximal triangulations of convex polytopes. March 8, 1999. Manuscript. Institut fur Theoretische Informatik,ETH-Zentrum, Zurich.

57. G. M. Ziegler. Lectures on 0/1-polytopes. Combinatorics and Computation, volume 29 of DMV Seminars, pages 1-41. Birkhauser-Verlag, Basel, 2000.

58. W.D Smith. A lower bound for simplexity of the n-cube via hyperbolic volumes. European J. Combin. 21(1) (2000), 131-137.

59. С.Н.Бернштейн. Собрание сочинений. M.: 1 — 105-106 (1952).

60. A. Bliss, F. Е. Su. Lower bounds for simplicial covers and triangulations of. cubes, Discrete Comput. Geom. 33 (2005), 669-686.

61. R. W. Cottle. Minimal triangulation of the 4-cube. Discrete Math., 40(1):25—29, 1982.

62. R. B. Hughes. Lower bounds on cube simplexity. Discrete Math., 133(1-3):123—138, 1994.

63. R. B. Hughes and M. R. Anderson. Simplexity of the cube. Discrete Math., 158(l-3):99—150, 1996.

64. D. Orden, F. Santos. Asymptotically efficient triangulations of the d-cube. Discrete and Computational Geometry 30(4): 509-528 (2003).

65. J. F. Sallee. A triangulation of the n-cube. Discrete Math., 40(l):81-86, 1982.

66. А. А. Глазырин, А. С. Тарасов. Анти-Дюрер гипотеза для невыпуклых многогранников. Успехи математических наук, 64(2009), номер 3, 179180.

67. А.А. Глазырин, О новом свойстве полиэдральных разбиений, Материалы IX Международного семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О. Б. Лупанова, 2007, стр. 377-379.

68. А. А. Глазырин. О симплициальных разбиениях многогранников. Математические заметки, 85(2009), номер 6, 840-848.

69. D. Frettloh, A. Glazyrin. The lonely vertex problem. Beitrage zur Algebra und Geometrie vol.50, No.l 2009, 71-79.

70. A. Akopyan, A. Glazyrin, О. Musin, A. Tarasov. The extremal spheres theorem, http://arxiv.org/abs/0906.3823

71. A.A. Глазырин. Симплициальные разбиения кубов. Деп. в ВИНИТИ РАН 30.10.2009, №679-В2009, 15 с.

72. А.А. Глазырин. Многомерная теорема о четырех вершинах. Деп. в ВИНИТИ РАН 30.10.2009, №678-В2009, 15 с.