Минимально-линейные вложения графов

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

Облакова Татьяна Александровна МИНИМАЛЬНО-ЛИНЕЙНЫЕ ВЛОЖЕНИЯ ГРАФОВ 01.01.04 геометрия и топология

АВТОРЕФЕРАТ

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

Москва 2013

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

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

Официальные оппоненты: Семенов Павел Владимирович доктор физико-математических наук, профессор (ГБОУ ВПО Московский городской педагогический университет, кафедра математического анализа и методики преподавания математики, зав.кафедрой) Карасев Роман Николаевич доктор физико-математических наук, доцент (Московский физико технический институт (государственный университет), кафедра высшей математики, доцент)

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

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

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

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

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор Иванов Александр Олегович

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

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

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

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

В задаче суперпозиции возникают базисные вложения1. К. Борсуком было введено понятие k–регулярных вложений компактов2. Эти вложения возникают в задачах интерполяции и аппроксимации. Болтянский, Рышков и Шашкин исследовали k–регулярные вложения для случая полиэдров3.

Также ими занимались С.А. Богатый и В.М. Вылов4,5.

Вложения, рассматриваемые в первой части, являются обобщением k– регулярных вложений. Богатый6 доказал, что всякое отображение f : X R3 одномерного компакта в R3 сколь угодно малым изменением может быть превращено в такое вложение f : X R3, что на всякой прямой в R3 будет лежать не более четырех точек образа f (X) компакта X.

Укажем, что существование таких экономичных вложений доказал так же Гудселл7.

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

На вложения, рассматриваемые во второй части, накладываются более P. Ostrand Dimension of metric spaces and Hilbert’s problem 13. Bull. Amer. Math. Soc, 1965, v. 7, pp. 619–622.

K. Borsuk On the k–independent subsets of the Euclidean space and of the Hilbert space. Bull. Acad.

Sci. Pol., 1957, v. 5, №4, pp. 351– В.Г. Болтянский, С.С. Рышков, Ю.А. Шашкин О k-регулярных вложениях и их применении к теории приближения функций. УМН 1960, т. 15, №6 стр. 125– С.А. Богатый Гипотеза Борсука, препятствие Рышкова, интерполяция, аппроксимация Чебыше ва, трансверсальная теорема Тверберга, задачи. Труды матем. ин-та им. В.А. Стеклова, 2002, т. 239, стр. 63–82.

С.А. Богатый, В.М. Вылов Вложения Робертса и обращение трансверсальной теоремы Тверберга.

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

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

R.T. Zivaljevi The Tverberg-Vrecica problem and the combinatorial geometry on vector bundles. Israel c J. Math., 1999, v. 111, pp. 53–76.

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

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

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

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

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

Облаковым.

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

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

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

J.C. Mairhuber On Haar’s theorem concerning Chebyshev approximation problems having unique solu tions Proc. Amer. Math. Soc. 1956, 7, №4, pp. 609– Аппробация диссертации. Результаты диссертации неоднократно докладывались на научно-исследовательских семинарах и конференциях.

• научно-исследовательский семинар по общей топологии им. П. С.

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

Список приведен в конце автореферата [1-3].

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

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

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

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

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

Очевидно, что если граф k–вложим, то он l–вложим для каждого l k.

Прямая, на которой содержится не менее чем k точек образа графа, называется k–прямой.

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

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

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

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

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

Также в первой части доказана следующая теорема:

Теорема 3. 2–вложимость графа в R3 эквивалентна его планарности.

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

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

Предложение 2. Графы K3,n для n 6 являются 3–вложимыми.

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

Вторая часть посвящена числу гиперпланарности графов. Числом n– гиперпланарности графа называется минимум по всем вложениям данного графа в n–мерное пространство максимального числа точек образа, принадлежащих гиперплоскости. Основной конструкцией для анализа вложений с малым числом гиперпланарности является моментная кривая (t, t2, t3,..., tn ).

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

Теорема 5. Для любого дерева G при n 3 существует вложение в n–мерное пространство такое, что число гиперпланарности образа не превосходит n + k 1. Здесь k минимальное число отрезков Ai, которыми можно покрыть дерево G так, что любые два отрезка могут пересекаться только по вершине графа.

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

Из результатов К. Облакова выводится следующее:

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

deg vi 1 +n deg vi Доказывается теорема:

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

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

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

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

Утверждение 2. Для любого натурального числа m число 2–планарности графа K1,m равно трем.

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

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

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

двумерная поверхность в R4, в системе Утверждение 3. Пусть M координат OXY ZU заданная как пересечение следующих двух гиперповерхностей:

M1 : x2 + y 2 + z 2 = 1;

M2 : x2 + (y G)2 u2 = где G некоторое действительное число, большее чем 2. Эта поверхность топологически эквивалентна несвязному объединению двух сфер, и ее чис ло 2–планарности равно 4.

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

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

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

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

механика, 2011, №2, стр. 54–56.

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

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