Минимально-линейные вложения графов тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

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

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

Облакова Татьяна Александровна

МИНИМАЛЬНО-ЛИНЕЙНЫЕ ВЛОЖЕНИЯ ГРАФОВ

01.01.04 — геометрия и топология

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

Москва 2013

005060823

005060823

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

Научный руководитель: доктор физико-математических наук,

профессор Богатый Семеон Антонович

Официальные оппоненты: Семенов Павел Владимирович

доктор физико-математических наук, профессор (ГБОУ ВПО Московский городской педагогический университет, кафедра математического анализа и методики преподавания математики, зав.кафедрой)

Карасев Роман Николаевич доктор физико-математических наук, доцент (Московский физико-технический институт (государственный университет), кафедра высшей математики, доцент)

Ведущая организация: ФГБОУ ВПО „Петрозаводский

государственный университет ".

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

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова (Ломоносовский проспект 27, сектор А, 8-й этаж).

Автореферат разослан 22 февраля 2013 года.

Ученый секретарь

диссертационного совета

Д.501.001.84 при МГУ

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

профессор

Иванов Александр Олегович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Работа представляет собой исследование в области геометрии- и топологии Евклидовых пространств и теории графов, вложений графов в евклидово пространство.

Различные вложения графов рассматривались в математике в течение последнего полувека. Классическими стали теоремы о вложении произвольного графа в трехмерное пространство, о минимальности и полноте семейства графов Куратовского-Понтрягина с точки зрения невложимости в плоскость.

В задаче суперпозиции возникают базисные вложения1. К. Борсуком было введено понятие fc-регулярных вложений компактов2. Эти вложения возникают в задачах интерполяции и аппроксимации. Болтянский, Рышков и Шашкин исследовали fc-регулярные вложения для случая полиэдров3. Также ими занимались С.А. Богатый и В.М. Былов4'5.

Вложения, рассматриваемые в первой части, являются обобщением к-регулярных вложений. Богатый6 доказал, что всякое отображение /: X —» —* R3 одномерного компакта в R3 сколь угодно малым изменением может быть превращено в такое вложение f€: X —> R3, что на всякой прямой в R3 будет лежать не более четырех точек образа f£(X) компакта X. Укажем, что существование таких «экономичных вложений» доказал также Гудселл7.

Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности «экономичных» отображений, но и на уровне теоремы существования. Именно, Живалевич8 доказал, что для всякого вложения Kßfi в R3 существует прямая, пересекающая граф не менее чем но четырем точкам. В данной работе этот результат усилен.

На вложения, рассматриваемые во второй части, накладываются более

'Р. Ost,rand Dimension of metric spaces and Hubert's problem IS. Bull. Amer. Math. Soc, 1965, v. 7, pp. 619-622.

2K. Borsuk On the k-independent subsets of the Euclidean space and of the Hilbert space. Bull. Acad. Sei. Pol., 1957, v. 5, №4, pp. 351-356

3В.Г. Болтянский, С.С. Рышков, Ю.А. Шашкин О к-регулярпых вложениях и их применении к теории приближения функций. УМН 1960, т. 15, №6 стр. 125-132

4С.А. Богатый Гипотеза Барсука, препятствие Рышкова, интерполяция, аппроксимация Чебыихе-ва, трансверсалъпая теорема Тверберга, задачи. Труды ыатем. ин-та им. В. А. Стеклова, 2002, т. 239, стр. 63-82.

5С.А. Богатый, В.М. Вылов Вложения Робертса и обращение трансверсальной теоремы Тверберга. Матем. сб., 2005, т, 196, №11, стр. 33-52

6С. А. Богатый Цветная теорема Тверберг. Вести. Мое. Ун-та, сер. 1, математика, механика, 1999, №3 стр. 14-19.

7T.H. Goodsell Strong general position and Menger curses Topol. Appl., 2002, v. 120, №1-2, pp. 47-55.

SR.T. ¿ivaljevié The Tverberg-Vrecica problem and the combinatorial geometry on vector bundles. Israel J. Math., 1999, v. Ill, pp. 53-76.

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

Цель работы: исследовать минимальные графы, при любом вложении которых в трехмерное евклидово пространство найдется прямая, содержащая не менее четырех точек образа. Изучить вложения графов в евклидово пространство, при которых минимально возможное число точек образа принадлежит гиперплоскости. Найти точную верхнюю оценку минимального числа точек данного графа, принадлежащих гиперплоскости. Доказать точность нижней оценки числа точек образа графа, принадлежащих гиперплоскости, полученной К. Облаковым. Изучить вложения графов в четырехмерное пространство, при которых минимальное число точек принадлежит двумерной плоскости.

Научная новизна. Результаты диссертации являются новыми. Укажем наиболее важные результаты:

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

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

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

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

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

9J.C. Mairhuber On Haar's theorem concerning Chebyshev approximation problems having unique solutions Proc. Amer. Math. Soc. 1956, 7, №4. pp. 009-615

Аппробация диссертации. Результаты диссертации неоднократно докладывались на научно-исследовательских семинарах и конференциях.

• научно-исследовательский семинар по общей топологии им. П. С. Александрова (семинар кафедры общей топологии и геометрии механико-математического факультета МГУ) под руководством профессоров В.В. Федорчука, Б.А. Пасынкова, В.И. Пономарева, С.А. Богатого и В.В. Филиппова неоднократно (2007, 2008, 2009, 2011)

• XV международная конференция студентов, аспиратнов и молодых ученых «Ломоносов-2008», Москва, МГУ

• Международная топологическая конференция «Александровские чтения» (май 2012), Москва, МГУ

Публикации. По теме диссертации автором опубликовано 3 работы. Список приведен в конце автореферата [1-3].

Структура и объем работы. Диссертация изложена на 44 страницах и состоит из введения, 3 глав и списка литературы, включающего 17 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая часть посвящена изучению следующего свойства графов:

Определение 1. Граф называется к-вложимым, если существует такое вложение в К3, что на любой прямой находится не более к точек графа.

Очевидно, что если граф /г-вложим, то он ¡-вложим для каждого I > к. Прямая, на которой содержится не менее чем к точек образа графа, называется ^-прямой.

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

Теорема 1. Графы Петерсена являются минимальными не 3-вложимьши графами.

В доказательстве используется следующее утверждение:

Теорема 2. Для любого вложения двух окружностей в К.3 с ненулевым числом зацепления имеется А-прямая.

Доказывается 3-вложимость графов Петерсена без ребра. Предъявляются 3-вложения графов в пространство с помощью так называемой конструкции с «шапочкой» — объединения единичной сферы и сегмента сферы большего радиуса, граничная окружность которого лежит на единичной сфере. Также в первой части доказана следующая теорема:

Теорема 3. 2-вложимостъ графа в М3 эквивалентна его планарности.

Кроме того, доказана 3-вложимость нескольких непланарных графов:

Предложение 1. Букет двух графов Куратовского-Понтрягина 3-вложим.

Предложение 2. Графы К3. п для п ^ 6 являются 3-вложимыми.

Теорема 4. Граф, полученный из графа Куратовского-Понтрягина увеличением кратности ребер, является 3-вложимым.

Вторая часть носвящена числу гиперпланарности графов. Числом п-гииернланарности графа называется минимум но всем вложениям данного графа в 7г-мерное пространство максимального числа точек образа, принадлежащи гиперплоскости. Основной конструкцией для анализа вложений с малым числом гиперпланарности является моментная кривая (і, і2, і3,... , і"). Основным результатом является следующая теорема:

Теорема 5. Для любого дерева (3 при п > 3 существует вложение в п-мерное пространство такое, что число гиперпланарности образа не превосходит п + к — 1. Здесь к — минимальное число отрезков А{, которыми можно покрыть дерево б так, что любые два отрезка могут пересекаться только по вершине графа.

Путем соединения фрагментов моментной кривой строятся вложения деревьев в евклидовы пространства, при которых число точек образа, принадлежащих гиперплоскости, не превосходит п + к — 1. Из результатов К. Облакова выводится следующее:

Следствие 1. Пусть размерность пространства не меньше числа вершин дерева степени 3 и выше. Тогда число гиперпланарности дерева не меньше следующего числа:

Доказывается теорема:

Теорема 6. Если размерность пространства не меньше числа вершин дерева степени 3 и выше, верхняя оценка числа гипертгланарности для дерева, полученная в теореме 5, совпадает с нижней оценкой, полученной в следствии 1.

Третья часть посвящена минимально-линейным вложениям графов в четырехмерное пространство. Случай пересечения графа гиперплоскостью рассматривается во второй части. Случай прямой исчерпывающе описывается следующим утверждением:

Утверждение 1. Любой граф можно вложить в п-мерное пространство при п > 3 так, что на любой прямой содержится не более двух точек образа графа.

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

Утверждение 2. Для любого натурального числа т число 2-планарности графа Кіг1п равно трем.

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

Теорема 7. Число 2-планарности любого планариого графа не превышает 4.

Для конструировании вложений с малым числом 2-нланарности используется поверхность М:

Утверждение 3. Пусть М — двумерная поверхность в К4, в системе координат ОХУЕІІ заданная как пересечение следующих двух гиперповерхностей:

Мі : х2 + у2 + = 1;

М2 : я2 + (у - в)2 - и2 = 1

где (7 — некоторое действительное число, большее чем 2. Эта поверхность топологически эквивалентна несвязному объединению двух сфер, и ее число 2-планарности равно 4.

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

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1) Антонова Т.А., Облаков К.И. Специальные вложения графов в трехмерное пространство Вестн. Моск. Ун-та, сер. 1, математика, механика, 2008, №6, стр. 26 31.

Автором получены результаты, кроме доказательства 3-вложимости конфигураций г) и е) на "шапочке".

2) Облаков К.И., ОблаковаТ.А. Специальные вложения некоторых несвязных графов в трехмерное пространство. Вестн. Моск. Ун-та, сер. 1, математика, механика, 2011, №2, стр. 54-56.

Автору принадлежит утверждение 2.

3) Облаков К.И., Облакова Т.А. Вложения графов в евклидово пространство, при которых число точек, принадлежащих гиперплоскости, минимально. Матем.сб., 201:10 (2012), 145-160

Автору диссертации принадлежат верхняя оценка числа гииерпланарности для деревьев и ассимптотические свойства оценок.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж /10 экз. Заказ №

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи 04201357128 УДК 515.162.6+515.125

Облакова Татьяна Александровна

МИНИМАЛЬНО ЛИНЕЙНЫЕ ВЛОЖЕНИЯ ГРАФОВ

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель — доктор физико-математических наук, профессор С.А. Богатый

Москва 2013

Содержание

Введение. 3

1 Минимизация количества точек образа графа на прямой. 5

1.1 Основные определения............................5

1.2 Зацепленные окружности..........................5

1.3 «Шапочка» и графы Петерсена..................7

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

1.5 2-вложимость......................................17

1.6 Несколько примеров................................19

1.7 Конструкция с «кепочкой»........................20

1.7.1 Конструирование почти выпуклой пленки............................................20

1.7.2 Конструирование «кепочки»..............23

1.7.3 Трехузловые графы........................24

1.8 О конкретных примерах 4-вложений графов. . 26

2 Минимизация числа точек графа, принадлежащих гиперплоскости 28

2.1 Необходимые определения и свойства..........28

2.2 Верхняя оценка числа гиперпланарности для случая деревьев....................................30

2.3 Ассимптотические свойства оценок..............32

3 Случай четырехмерного пространства. 35

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

3.2 Графы с наименьшим числом 2-планарности. 35

3.3 Конструирование поверхности с малым числом 2-планарности......................................37

3.4 Вложение планарных графов......................41

3.5 Минимальность пары триодов....................41

Введение.

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

Вопросы вложения графов являются важной частью теории графов. Известно, что любой граф можно вложить в М3. Часто бывает важно среди всех вложений графа в евклидово пространство выделить множество некоторых специальных вложений. В задаче суперпозиции возникают базисные вложения [1]. В задачах интерполяции и аппроксимации возникают /с-регулярные вложения [2]. Вложения, рассматриваемые в первом разделе диссертации — вложения графов, при которых минимальное число точек образа принадлежит прямой — являются обобщением /¿-регулярных вложений. Богатый [3] доказал, что всякое отображение /: X —> К3 одномерного компакта в М3 сколь угодно малым изменением может быть превращено в такое вложение /е: X —>• К3, что на всякой прямой в М3 будет лежать не более четырёх точек образа /£(Х) компакта X. Укажем, что существование таких «экономичных вложений» доказал также Гудселл [5]. Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности «экономичных» отображений, но и на уровне теоремы существования. Именно, Живалевич доказал, что для всякого вложения в К3 существует прямая, пересекающая граф не менее чем по четырем точкам [6]. Автором доказано наличие такой прямой для меньших графов (граф К4.4 без ребра является подграфом -К'б.б), таким образом усилен результат Живалевича.

Вторая часть посвящена числу гиперпланарности графа — минимальному по всем вложениям графа в Евклидово пространство заданной размерности числу точек образа графа, принадлежащих одной гиперплоскости. Получена верхняя оценка числа гиперпланарности для деревьев, линейно зависящая от размерности пространства и комбинаторных характеристик графа. Для пространств больших размерностей эта оценка совпадает с нижней оценкой, полученной К. Облаковым. Кроме результатов К. Облакова, практически единственным результатом, касающимся этого семейства вложений, является теорема Мэрхьюбера о том, что любое компактное множество в п-мерном пространстве, содержащее не более п точек на любой гиперплоскости, является гомеоморфным образом замкнутой части окружности [18].

В третьей части рассматриваются вложения графов в четырехмерное Евклидово пространство, при которых минимальное число точек принадлежит двумерной плоскости. Этот вопрос представляет собой обширную область для изучения. Из результата Богатого из [3] следует, что любой граф можно вложить в четырехмерное пространство таким образом, что на любой двумерной плоскости содержится не более шести точек. Для выведения оценок числа точек образа графа, принадлежащих двумерной плоскости при вложениях в четырехмерное пространство также может быть использована теорема Скопенкова (см. [17], теорема 1.4.1). Автором доказано, что любой планарный граф может быть вложен в четырехмерное пространство таким образом, что любая двумерная плоскость содержит не более четырех точек образа. Также получены вложения окружности и графа т—

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

1 Минимизация количества точек образа графа на прямой.

1.1 Основные определения

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

Определение 1. Граф называется п-вложимым, если существует вложение в М3 такое, что на любой прямой находится не более п точек графа.

Очевидно, что если граф п-вложим, то он /с-вложим для любого к > п. Будем называть п-прямой прямую, содержащую п точек образа графа.

В данной работе мы рассматриваем вопрос п-вложимо-сти графов для различных п.

4-вложимость всех графов следует из теорем, доказанных в [4], [5].

Случаю 3-вложимости посвящены теоремы 2 и 5. Харак-теризация всех 2-вложимых графов дается в теореме 10.

1.2 Зацепленные окружности.

Сформулируем необходимое условие 3-вложимости графа.

Теорема 2. Для любого вложения двух окружностей в К3 с ненулевым числом зацепления имеется 4-прямая.

Доказательство теоремы 2. Пусть это вложение : 5'1и и 51 —»• М3. Обозначим через X, У образы окружностей в пространстве. Через Т обозначим тор, являющийся прямым произведением окружностей X и У. Обозначим через А множество таких точек (х,у) С Т, что на луче (х, у) за точкой у найдётся еще хотя бы одна точка X. Множество пар (х, у) на торе таких, что на луче (у, х) за точкой х найдётся точка У обозначим через В. Если мы докажем, что А и В пересекаются, это будет означать наличие 4-прямой, причём эти четыре точки «зацеплены», то есть будут чередоваться точки окружностей X и У. Однократные обходы X и У являются образующими фундаментальной группы тора Т.

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

Лемма 3. Носитель замкнутого пути на торе, нетривиально обходящий вдоль У, содержит точку А, и носитель замкнутого пути, нетривиально обходящий вдоль X, содержит точку В.

Лемма 4. Множества А «В замкнуты.

Теперь докажем теорему от противного. Предположим, что А и В не пересекаются. Так как они замкнуты, расстояние между ними ненулевое и равно некоторому числу <5. Выберем на торе конечное число параллелей и меридианов таким образом, чтобы расстояние от каждой точки тора до ближайшей параллели и ближайшего меридиана не превышало <5/12. Дополнение объединения этих параллелей и меридианов на торе представляет собой несвязное объединение открытых множеств — будем называть их клетками. Клетки, замыкания которых пересекаются, будем называть соседними. Так как диаметр каждой клетки меньше 6, ни одна клетка не может содержать как точки множества А, так и точки множества В. Более того, в силу выбора расстояния между параллелями и меридианами не может быть и двух соседних клеток таких, что одна из них содержит точку множества А, а другая — точку множества В.

Обозначим за А замыкание объединения всех клеток, содержащих точки множества А, аналогично введем множество В. Из вышесказанного следует, что множества А и В не пересекаются. Так как А £ А, и В € В, носитель замкнутого пути на торе, нетривиально обходящий вдоль V, содержит точку А, и носитель замкнутого пути, нетривиально обходящий вдоль X, содержит точку В. Введем еще одно обозначение: О = Т \ (А У В).

Для заданного разбиения тора на конечное число клеток существует конечное число разбиений этих клеток на множества А, В и Назовем допустимым такое разбиение, для которого выполняются следующие свойства:

1) нет соседних клеток, таких что одна из них принадлежит А, а другая В.

2) Носитель любого замкнутого пути на торе, нетривиально обходящего вдоль Y, содержит точку А, а нетривиальный обходящий вдоль X, содержит точку В.

Из сделанного выше предположения следует, что как минимум одно допустимое разбиение существует. Введем на множестве допустимых разбиений следующую функцию: Ф = L(A) + L(B) + L(Q), где функция L(C) — число компонент линейной связности множества С. Функция определена на непустом конечном множестве, а значит, достигает минимума. Будем в дальнейшем рассматривать разбиение £ — одно из тех разбиений, на которых функция Ф достигает минимум.

_ Пусть е — минимальная длина стороны клетки. Пусть А — объединение множества А и всех точек тора, находящихся на расстоянии < е/4 от множества А. Граница дА этого множества представляет собой несвязное объединение гладких Жордановых кривых, лежащих в множестве Q. Пусть 7 — одна из них. Так как разбиение £ допустимо, кривая 7 не может содержать нетривиального обхода вдоль X или Y. Пусть С — та из компонент связности множества Т \ 7, которая гомеоморфна двумерному диску. Рассмотрим два случая:

1) множество С содержит компоненту линейной связности А или В. В таком случае построим разбиение £1, отличающееся от £ тем, что клетки, входящие в эту компоненту, будут отнесены к множеству Q.

2) множество С входит в il Построим разбиение £1, отличающееся от £ тем, что все клетки, имеющие непустое пересечение с С, будут отнесены к множеству А

В обоих случаях легко проверить, что разбиение £1 допустимо, и что Ф(£г) < Ф(0- Полученное противоречие с минимальностью £ доказывает теорему 2 □

1.3 «Шапочка» и графы Петерсена.

Теорема 2 позволяет во многих случаях доказывать отсутствие 3-вложения. В работах [7]. [8], [10], [11] описаны все

графы, всякое вложение которых в К3 имеет пару окружностей с ненулевым числом зацепления. Именно, дан полный список минимальных графов, влекущих наличие окружностей с ненулевым числом зацепления. Такой полный список графов образуют графы семейства Петерсена (см. рис. 1). Так как теорема 2 даёт необходимое условие 3-вложимости, то графы Петерсена не являются 3-вложимыми, но вопрос о минимальности этих графов (с точки зрения существования 3-вложимости) и полноты этого списка остаётся открытым. Следующая теорема показывает, что все эти графы минимальны.

Теорема 5. Все графы семейства Петерсена являются минимальными Ъ-невложимыми графами.

Далее докажем 3-вложимость графов Петерсена без ребра. Предъявим 3-вложения графов в пространство с помощью так называемой конструкции с «шапочкой».

Определение 6. Конструкция с «шапочкой» — это объединение единичной сферы и сегмента сферы большего радиуса, граничная окруэюиостъ которого лежит на единичной сфере.

Граничную окружность сегмента будем называть границей «шапочки». Она разбивает единичную сферу на две части. Объединение той из частей, которая выпукла в ту же сторону, что и сегмент, с самим сегментом, будем называть, собственно, «шапочкой». Сегмент сферы большого радиуса будем называть нижним слоем «шапочки», сегмент единичной сферы — верхним слоем, а часть сферы, не входящую в «шапочку» — внешностью «шапочки». Сформулируем утверждение, доказательство которого дадим позже:

Утверждение 7. Вложение любой фигуры в конструкцию с «шапочкой», образ которой, пересеченный с самой «шапочкой» является подмножеством одной из фигур, изображенных на рис. 2, является 3-вложением.

Изображены проекции конструкций на плоскость а. содержащую границу «шапочки». Пунктирные линии принадлежат нижнему слою «шапочки», а сплошные — верхнему.

Рис. 1. Семейство графов Петерсена: граф К§ и графы образованные из него операциями ДY и YД.

а) б) в) г) д) е)

Рис. 2. 3-вложимые конфигурации на „шапочке"

Изображенные в виде отрезков линии на «шапочке» являются дугами больших окружностей соответствующих сфер. Доказательство теоремы 5. 3-невложимость графов Пе-терсена является очевидным следствием теоремы 2, так как, согласно теореме Робертсона-Сеймура-Томаса, все они имеют пару зацепленных окружностей при любом вложении в М3. Для доказательства минимальности этих графов вложим каждый из графов Петерсена без одного ребра в одну из 3 вложимых конструкций на «шапочке».

Заметим, что у К§ все ребра эквивалентны друг другу, и потому не важно, которое из них мы удалим. Для 3-вложения К§ без ребра воспользуемся конструкцией д) на «шапочке». Вершины 1 и 2 поместим, соответственно, на верхний и нижний слои «шапочки». Ребро 5-6 отсутствует (см. рис. 4 а)).

Аналогичным образом на рис. 4 изображены 3-вложения графов Петерсена без всех возможных ребер с помощью 3-вложимых конфигураций на «шапочке». На рисунках окружность всегда изображает только границу «шапочки», пунктирными линиями изображено то, что лежит на нижнем слое «шапочки», сплошные линии внутри круга изображают содержимое верхнего слоя, сплошные линии вне круга изображают содержимое внешности «шапочки» . Минимальность графов Петерсена доказана. □

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

Доказательство леммы 3. Предположим противное: пусть существует замкнутый путь 7: [0,1] —> Т, нетривиально обходящий У и не содержащий точек множества А.

Рассмотрим функции 7!: [0,1] —> X, 72: [0,1] —> У, являющиеся проекциями пути 7 на X и У. Заметим, что отображения 72 и /1: 51 —» X имеют ненулевое число зацепления. Действительно, число зацепления 72 и /1 равняется произведению числа зацепления X и У на кратность обхода путем 72 окружности У. Оба сомножителя ненулевые.

Пусть отображение К\ [0,1] х [0, оо) —>■ М3 построено следующим образом: /2.(5, ¿) = 72(5) + I • 71(5)72(5). При этом

5 —>

Без ребра 5-6.

Без ребра 3-5. Без ребра 5-7. Без ребра 1-3.

Г" :;2,зб|

гЛ ;

Без ребра 1-5. Без ребра 4-8.

Без ребра 6-7. Без ребра 1-5.

\6

Без ребра 5-6. Без ребра 3-4. Без ребра 1-7.

3

Рис. 3. 3-вложения графов Петерсена без ребра

/¿(5,0) = 72(5), и уходит на бесконечность при Ь -л

—> оо. Исходя из определения множества А, для каждой точки (х,у) = (71(5),72(5)) £ Т носителя пути 7 на луче (х, у) за точкой у не найдется других точек X. Потому образ /¿(5, £) не пересекает X. Мы построили гомотопию отображения 72 в отображение на бесконечность, не пересекая отображения /1: 51 —>■ X. Это означает, что число зацепления /1 и 72 стало нулевым. Противоречие. Для X и В доказывается аналогично. □

Доказательство леммы 4. Рассмотрим последовательность (хг,уг) С А, (хг,уг) —> (х,у). Пусть хг — точка множества X, лежащая на луче (хг,уг) за точкой уг. Так как {¿г} — бесконечная последовательность на компакте X, то у неё есть сходящаяся подпоследовательность. Без ограничения общности считаем, что это {¿г}.

Прямые хгуг = хгхг сходятся к прямой ху, откуда следует, что Х\ лежит на ху за точкой у, так как соотношение хгхг =

А • хгуг (Л > 1) сохраняется и в пределе.

Полученное включение (ж, у) £ А, и означает, что А — замкнуто. Замкнутость В доказывается аналогично. □

Для доказательства утверждения 7 потребуется следующее утверждение:

Утверждение 8. Прямая пресекает конструкцию с «шапочкой» не более чем по 4 точкам, и 4-прямой может стать только прямая, пересекающая в двух точках верхний, и в двух точках — нижний слой «шапочки».

Доказательство утверждения 8. Если прямая I имеет точку М на внешности «шапочки», то она не может пересечь нижний слой более чем в одной точке, значит, 4-прямой она не является, откуда и получаем утверждение. □

Из этого утверждения тривиально следует, что любое вложение графа в конструкцию с «шапочкой» — 4-вложение. Доказательство утверждения 7. От противного, пусть 4-прямая нашлась. Рассмотрим проекцию получившейся картинки на плоскость а, содержащую границу «шапочки». Пользуясь утверждением 8 и тем, что проекции пересекающихся множеств на любую плоскость пересекаются, получим, что проекция 4-прямой обязана в двух точках пересечь

проекцию части образа, попавшей на верхний слой «шапочки», и в двух — попавшей на нижний слой. Причем обе точки нижнего слоя обязательно должны быть расположены между двумя точками верхнего слоя. Для фигур на рис. 2 6), в), г