Комбинаторные и вероятностные методы в задаче о геометрических числах Рамсея тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Московский государственный университет имени М.В. Ломоносова

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

/Ы

Титова Мария Викторовна

Комбинаторные и вероятностные методы в задаче о геометрических числах Рамсея

01.01.05 — теория вероятностей и математическая статистика, 01.01.09 — дискретная математика и математическая кибернетика

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

21 НОЯ 2013

Москва — 2013

005539410

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

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

профессор Райгородский Андрей Михайлович.

Официальные оппоненты: доктор физико-математических наук, зав.

лабораторией теории вероятностей и компьютерной статистики ФГБУН Институт прикладных математических исследований Карельского научного центра РАН, профессор Павлов Юрий Леонидович;

кандидат физико-математических наук, доцент кафедры математической логики и высшей алгебры факультета ВМК ННГУ Малышев Дмитрий Сергеевич.

Ведущая организация: Хабаровское отделение Института

прикладной математики ДВО РАН.

Защита диссертации состоится 13 декабря 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/. Автореферат разослан_ноября 2013 г.

Ученый секретарь диссертационного совета

В.А. Костенко

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

Актуальность работы

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

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

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

Начиная с 1930 годов теория Рамсея стала активно развиваться и обрела популярность благодаря работам знаменитого венгерского математика Пола Эрдеша. Известные результаты теории Рамсея о геометрических и числовых множествах, ставшие стимулом ее дальнейшего развития, включают в себя теорему Эрдеша-Секереша о выпуклых многоугольниках, теорему Ван-дер-Вардена об арифметических прогрессиях, теорему Хэйлса-Джуита об игре в многомерные крестики-нолики, теорему Шура, а также множество ее обобщений, таких как теоремы Радо, Радо-Фолкмана-Сандерса, Хиндмана. Большой обзор по результатам теории Рамсея предоставлен в книге Грэхема, Ротшильда, Спенсера2.

Одной из классических задач теории является задача о нахождении чисел Рамсея, которые возникают в формулировке теоремы Рамсея. В

'F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser., 2 (30), 1930, 264-286.

2R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory., 2nd ed., John Wiley and Sons, NY. 1990.

1947 году Эрдеш3 впервые применительно к задачам такого типа использует вероятностный подход — так называемую случайную раскраску.

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

Одно из обобщений классических чисел Рамсея — дистанционные числа Рамсея — служит предметом изучения данной диссертационной работы. Это понятие возникает в связи с известной задачей комбинаторной геометрии об исследовании свойств конечных дистанционных графов.

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

В первую очередь интерес к задачам комбинаторной геометрии подняли многочисленные работы Пола Эрдеша. В 1935 году выходит статья Эрдеша-Секереша4, решающая обобщение задачи Клейн о выпуклых четырехугольниках с помощью теории Рамсея.

В работе 1946 года Эрдеш5 ставит вопросы о наибольшем числе единичных расстояний в множестве из п точек на плоскости и о числе различных расстояний, которые в числе прочих дают начало исследованиям различных свойств графов расстояний.

Следующие задачи стали ключевыми для образования и истории комбинаторной геометрии. Первая из них — это гипотеза Борсука0 о разбиении множеств на части меньшего диаметра. Речь идет о следующей задаче. Обозначим через f(d) минимальное количество частей меньшего диаметра, на которые можно разбить произвольное множество диаметра 1 в пространстве Rd. В 1933 году Борсук высказал гипотезу, что f(d) — d+1. Опровержение гипотезы стало одним из важнейших событий в комбинаторной геометрии последних десятилетий. Вторая задача — это

3Р. Erddfe, Some Remarb on the Theory of Graphs, Bulletin of the American Mathematical Society, 53, 1947, 292-294.

4P. Erdas, G. Szekeres, A combinatorial problem in geometry, Compositio Math., 2, 1935, 403-470.

5P. Erdfls, On a set of distances of n points, Anier. Math. Monthly, 53, 1940, 248-250.

6K. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundameiita Math., 20, 1933, 177-190.

проблема Нелсона-Хадвигера7,8'0 о раскраске метрических пространств. Задача была поставлена Нелсоном в 1950 году, а также независимо незадолго до этого похожая проблема изучалась Хадвигсром. Проблема формулируется так: необходимо найти хроматическое число равное минимальному количеству цветов, в которые можно так раскрасить все точки в евклидовом пространстве R¿, чтобы между одноцветными точками не было расстояния, равного единице.

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

Источниками дискретной геометрии можно считать несколько течений, появившихся в начале XX века. Во-первых, в 189G году выходит книга Минковского "Геометрия чисел"12, которая рассказывает о связях между теорией чисел и выпуклой геометрией. Дальнейшее развитие этой связи рассматривается в книгах Касселса13, Кокстсра14, Тота15 и других.

Задача отыскания плотнейших упаковок является одной из наиболее значимых задач дискретной геометрии. Она ведет свое начало из знаменитой гипотезы Кеплера о плотнейшей упаковке шаров (которая рассматривалась Гильбертом как часть 18 проблемы). В середине прошлого века Тот и Роджерс использовали новые комбинаторные подходы к классическим проблемам, поставленным Ньютоном, Гауссом, Минковским, Гильбертом и Туе. Тем самым они начали развитие теории упаковок и

7Р.К. Agarwal, J. Pach, Combinatoria! Geometry, Wiley-Iuterscience Series in Discreto Míitliemutics and Optimization, John Wiley and Sons, 1995.

8P. Brass, W. Moser, J. Pach, Research problema in iisertte geometry, Springer, New York, 2ÜU5.

9A.M. Райгородскяй, Хроматические числа, Москва, МЦНМО, 2003.

10V.G, Boltyanski, Н. Maxtini, P.S. Soltan, Excursions into combinatoriaI geometry, Universitext, Springer, Berlín, 1997

11P. Brasa, W. Moser, J. Pacli, Research problems in discrete geometry, Springer, New York, 2005.

12H. Minkowski, Geometrie der Zahlen, RG Teubner, Leipzig-Berliii, 1953.

13Дж. Касселс, Введение в геометрию чисел, Москва, Мир, 1965.

"H.S.M. Coxeter, Regular Polytopes, Dover edition (3rd ed.), 1973.

15Л. Ф. Тот, Расположения на плоскостии, сфере и в пространстве, Москва, Физмалит, 1958.

покрытий16.

Многие из перечисленных задач комбинаторики, а также комбинаторной и дискретной геометрии решались при помощи вероятностного метода. Вероятностный метод применительно к этим задачам возник в конце первой половины XX века. Первой работой, в которой эта техника была введена, считается уже вышеупомянутая работа Эрдеша 1947 года, где он приводит вероятностное доказательство нижней оценки числа Рамсея. Можно найти и более ранние работы, в которых уже использовался вероятностный способ получения результатов. Самые известные из них — работа Турана17 1934 года (простое доказательство теоремы Харди-Рамануджана) и теорема Селе18 1943 года о существовании турнира с большим количеством гамильтоновых путей. Однако именно Эр-деш начал активное развитие вероятностного метода как мощного инструмента для решения задач комбинаторики и экстремальной теории графов и внес в него за следующие почти 50 лет значительный вклад. В последующие годы метод позволил установить множество утверждений в теории чисел, анализе, теории информации, дискретной математике. Многие результаты теории кодирования также доказываются с помощью вероятностных идей.

Именно применение вероятностного метода позволило получить Эр-дешу первую нижнюю оценку числа Рамсея. Еще один пример известной задачи, где метод позволил получить неожиданно эффективный результат, — это задача Эрдеша-Фюреди19 об остроугольных треугольниках. В работе был построен изящный и простой контрпример к гипотезе Дан-цера и Грюнбаума, державшейся 20 лет. Небольшое усовершенствование данного метода — метод малых вариаций — позволило получить простое доказательство классического результата комбинаторики и теории графов — теоремы Эрдеша20 о том, что существуют графы с наперед заданным хроматическим числом и обхватом. Речь идет о следующем

16Дж. Конвей, Н. Слоэн, Упаковки шаров, решетки и группы, Москва, Мир, 1990.

1ТР. Türán, On a theorem of Hardy and Ramanujan, Journal of the London Mathematical Society, 9, 1934, 274-276.

I8T. Szele, Kombinatorikiii Vizsgílatok ai Irdnyitott Teljes Griffal Kapcsolatban, Mat. Fiz. Lapok, 50, 1943, 223-256.

lyP. Erdös, Z. Fflredi, The greatest angle among n point.« in the d-dimensional Euclidean space. Annals of Discrete Math., 17, 1983, 275-283.

mP. Erdas, Graph theory and probability, Cañad. J. Math., 11, 1959, 34-38.

вопросе: всегда ли для данных целых положительных g, к существует граф G с хроматическим числом не меньше к, содержащий только циклы длины не меньше gl

Независимо друг от друга в 1959 году Гильберт21, а также Эрдеш и Реньи22 определяют понятие случайного графа. Исследованиям случайного графа в моделях Эрдеша—Реньи G(N,p) за последние десятилетия посвящено огромное количество работ. В частности, исследовались чадами о распределении малых подграфов в случайном графе, распределении количества деревьев, о поиске гигантской компоненты и определении ее размера, о распределении диаметра случайного графа, о моделях случайных геометрических графов. Приложение теории случайных графов было использовано и в упомянутой выше проблеме Нелсона-Хадвигера о раскраске метрических пространств.

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

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

Цель работы

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

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

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

21E.N. Gilbert, Random graphs, Aimais of Mathematical Statistics, 30, 1959, 1141-1144.

"P. ErdSs, A. Rényi, On random graphs, I, Publ. Math. Debrecen, ß, 1959, 290-297.

из них:

1. Предложены три метода для получения оценок дистанционного числа Рамсея.

2. Получены оценки дистанционного числа Рамсея, существенно улучшающие известные ранее.

3. Найдены оценки плотности множеств без расстояния единица в пространствах малых размерностей.

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

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

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

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

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

Результаты диссертации докладывались на следующих научно-исследовательских семинарах:

— Семинар "Вероятностные и алгебраические методы в комбинаторике" под руководством профессора A.M. Райгородского (мехмат МГУ, 2009-2012 гг., неоднократно).

— Кафедральный семинар кафедры математической статистики и случайных процессов под руководством профессора A.M. Зубкова (мехмат МГУ, 2013 г.).

— Семинар под руководством профессора В.Е. Бснинга, В.Ю. Королева (ВМК МГУ, 2013 г.)

— Семинар под руководством профессора В.Б. Алексеева, профессора АА. Сапоженко, профессора СА. Ложкина (ВМК МГУ, 2013 г.)

Результаты диссертации докладывались на следующих научных конференциях:

— X международный научный семинар "Дискретная математика и ее приложения" (Москва, 1-8 февраля 2010 г.)

— Научная конференция "Ломоносовские чтения" (Москва, 1G-22 апреля 2010 г.)

— Международная конференция "Конечные и бесконечные множества" (Будапешт, Венгрия, 13-17 июня 2011 г.).

— Международная конференция "Четвертая польская конференция по комбинаторике" (Бедлево, Польша, 17-21 сентября 2012 г.).

Публикации

Результаты диссертации опубликованы в 5 работах автора (3 из которых входят в перечень ВАК), список которых приведен в конце автореферата.

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

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

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

Введение к диссертации состоит из трех частей. В части "Теория Рам-сея" излагается история теории Рамсея, говорится о классической задаче о нахождении чисел Рамсея. В части "Комбинаторная и дискретная геометрия" дается круг задач комбинаторной и дискретной геометрии, близких к теме диссертации: это задача Эрдеша о наибольшем числе единичных расстояний на плоскости, проблема Нелсона-Хадвигера о раскраске метрических пространств, задача о плотнейшей упаковке шаров, и др. В части "Вероятностный метод" описывается история вероятностного метода и история его применения к задачам, упомянутым в первых двух частях введения.

Содержание главы 1

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

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

Дистанционным графом в d-мерном евклидовом пространстве называется граф G = (V,E), в котором множество вершин составляют точки пространства Rd и для которого выполнено

V(x,y)eS р(х, у) = а,

где а — фиксированное положительное число, р — обычная евклидова метрика в Rd. Везде далее мы полагаем а = 1.

Дистанционным числом Рамсея 7?neh(si t, d) называется такое минимальное натуральное п € N, что для любого графа Gen вершинами верно следующее: либо он содержит индуцированный подграф на s вершинах, изоморфный некоторому дистанционному графу в Rd, либо его дополнение G до полного графа на п вершинах содержит индуцированный подграф на t вершинах, изоморфный некоторому дистанционному графу в Md.

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

Содержание главы 2

Глава 2 посвящена двум методам получения нижних оценок дистанционного числа Рамсея в случае плоскости и трехмерного пространства. Оба метода построены на использовании случайного графа в модели Эрдеша-Реньи, локальной леммы Ловаса и специальных свойств, которыми обладают дистанционные графы на плоскости и в трехмерном пространстве. С помощью первого метода доказываются новые теоремы 4 и 5, при помощи второго — новые теоремы 6 и 7.

Теорема 4. Пусть d = 2. Имеет место следующее неравенство:

0.917 а-'

4

iWs, S, d) z ^=-(1 + о(1))А21, где k —4

Теорема 5. Пусть d = 3. Имеет место следующее неравенство:

Äneh(s, з, d) > + o(l))fc2*, где к = 8

Теорема 6. Пусть d = 2. Существует такая константа с > О, ■что

Теорема 7. Пусть d = 3. Существует такая константа с > О, что

где /3(s) = 2а3М, а a(s) - обратная функция Аккермана.

В конце главы рассматривается случай одномерного пространства.

В разделе 2.1 приводятся вспомогательные утверждения для получения оценок. В параграфе 2.1.1. дается утверждение I23, необходимое для доказательства теоремы 4.

Утверждение 1 (Кокоткин). В любом дистанционном графе на плоскости, имеющем п вершин, есть четыре независимых множества (т.е. множества вершин, свободные от ребер) суммарной мощности не менее [0.917п].

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

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

менее [з^]-

В параграфе 2.1.2 формулируются вспомогательные утверждения 3, 424 для доказательства теорем 6 и 7. А именно, оценивается количество ребер в дистанционном графе на плоскости и в пространстве.

Утверждение 3 (Бек, Спенсер). Найдется такая константа сг > О и такое П2 € N, что для всех п > щ и для любого дистанционного графа G — (V, Е) на плоскости, имеющего п вершин, < с^п^.

азА.А. Kokotten, A.M. Raigorodskii, On large subgraphs of distance graphs hailing small chromatic number, Abstracts of the talks at the international conference «Pete of combinatorics and computer science», Keszthely, Hungary, August, 2008.

"P. Brass, W. Moser, J. Paih, Research problems in discrete geometry, Springer, New York, 2005.

Утверждение 4 (Вельц, Гибас, Кларксон, Шарир, Эдельбруннер). Найдется такая константа с3 > 0 и такое n3 € N, чт,о для всех п > п3 и для любого дистанционного графа G = (V, Е) в R3, имеющего п вершин, |Я| < с3/3(п)п', где 0(п) = а а(п) - обратная функция

Аккермана.

В параграфе 2.1.3 дается формулировка локальной леммы Ловаса2и.

Теорема (локальная лемма Ловаса). Пусть Ai,...,An - события в произвольном вероятностном пространстве Р). Пусть также фиксированы числа р £ [0,1] и f < п - 1, причем ep(f + 1) < 1. Предположим, что P(A¿) < р для всех i и для любого i найдется такое множество событий S¡ С {А,.. ■, Ai} \ Л, что |Sj| ^ / и Ai не зависит от алгебры, порожденной событиями из множества {Ai,..., Ап} \ (Si U {Л}). Тогда имеет место неравенство Р (и Ai) > О, т.е. с положительной вероятностью ни одно из событий не выполнено.

В разделе 2.2 приводится доказательство теоремы 4. В разделе 2.3 приводится доказательство теоремы 5. В разделе 2.4 приводится доказательство теоремы 6. В разделе 2.5 приводится доказательство теоремы 7. В разделе 2.6 формулируется и доказывается теорема 14 для одномерного случая.

Теорема 14. Выполняется следующее неравенство:

Содержание главы 3

В данной главе получены результаты касающиеся плотнейших упаковок в пространствах размерности d = 3,..., 8, которые используются для обобщения одного из методов получения оценок дистанционного числа Рамсея, описанного в главе 2.

В разделах 3.1-3.4 рассматривается задача о плотнейших упаковках. Раздел 3.1 посвящен постановке задачи.

В параграфе 3.1.1 приводятся определения множества без расстояния единица и величины mi(Rd) — наибольшей плотности, которую может иметь множество без расстояния единица в пространстве Rd.

S!N. Alón, J.H. Spencer, The probabilistic method, 2nd ed., Jolui Wiley and Sons. New York, 2000.

На множестве 5 С К1 реализуется расстояние а, если найдутся такие точки х,у 6 5, что |х - у| = а, где через |х - у| обозначено евклидово расстояние между точками х и у в В противном случае мы называем & множеством без расстояния а. Верхней плотностью измеримого по Лебегу множества А С Е"* называется величина

_ ч — V (А П В9(г))

где ВЦ(г) обозначает шар радиуса г с центром в начале координат, а У(Х) — объем множества X.

т1 (К^) = вир 8{А),

АС№

где А — измеримое по Лебегу множество без расстояния единица.

В параграфе 3.1.2 приводятся необходимые определения из теории решеток и упаковок. В параграфе 3.1.3 рассматривается идея получения нижних оценок т^К1*). В параграфе 3.1.4 в теореме 15 формулируются основные результаты в задаче о плотнейших упаковках, а именно лучшие нижние оценки величины т^К^) при с? = 3,..., 8. Приводится сравнение новых результатов с известными ранее оценками.

Теорема 15. Имеют место следующие неравенства:

т 1(Е3) > 0.09877, тщ(Е6) ^ 0.00806, гщ(М4) 0.04413, Ш!(К7) > 0.00352, тщ(Е5) > 0.01833, 7П1(К8) > 0.00165.

Основной целью разделов 3.2-3.4 является построение как можно более плотных множеств без расстояния единица в К"2, (1 = 3,..., 8 для доказательства теоремы 15. В разделе 3.2 описывается конструкция множества без расстояния единица, с помощью которого Крофт получил лучшую оценку т^К2). В разделе 3.3 описывается конструкция для М3 и доказывается теорема 15 в случае <1 = 3. В разделе 3.4 описываются результаты в случаях й = 4,..., 8.

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

Теорема 8. Пусть d € {4,... ,8]. Выполняются следующие неравенства:

с4 = 0.04413, с5 = 0.01833, с6 = 0.00806, с7 = 0.00352, с8 = 0.00165.

Содержание главы 4

В данной главе описан метод, позволивший получить лучшие оценки дистанционного числа Рамсея для любого фиксированного d ^ 4, где d — размерность пространства. Основной результат главы — доказательство теоремы 9.

Теорема 9. Пусть d ^ 4 и 7 > 0. Тогда существует такое so = $o(d, 7), что при всех s > so выполняется неравенство

В разделе 4.1 формулируется вспомогательная теорема 16 об ограничении числа клик определенного размера в дистанционных графах, необходимая для доказательства теоремы 9. Теорема позволяет обобщить подход, использованный для получения оценок в теоремах 6 и 7. Пусть с/(<2, г) — число клик размера г (т.е. полных подграфов на г вершинах) в графе Н.

Теорема 16. Для любого d существует такое £ > 0 и существует, такое щ € М, что для всякого дистанционного графа й в на п ^ щ вершинах

В разделе 4.2 доказывается теорема 16. Раздел 4.3 посвящен доказательству теоремы 9.

В параграфе 4.3.1 описывается общая идея нахождения оценки дистанционного числа Рамсея. Рассказывается о применении результата

#neh(s, s. d) >-izrri1 + o(l))*^1, где k = [cds]

ÄNEH(s,S,d) ^Ukr1)'.

георемы 16 и использовании вероятностной техники для получения оценки теоремы 9.

Для каждого п рассматривается случайный граф в классической модели Эрдеша-Реньи G(n, 1/2). Для каждого подмножества S, ¡S| = s, множества Vn вершин случайного графа G (п, 1/2) определим событие ¿45, состоящее в том, что количество fc-клик индуцированного подграфа Я = G\s не больше sk~e. Пусть также A's — это событие, состоящее в том, что количество fc-клик графа Н = G|s не больше sk~*, где г — число из вспомогательной теоремы 16. Задача сводится к оценке вероятности событий As и A's.

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

Доказывается теорема 18 и следствие из нее.

Теорема 18. Справедливы неравенства

Следствие. При £¿ = 4,5 верна следующая нижняя оценка дистанционного числа Рамсея:

В параграфе 4.3.3 техника, описанная в параграфе 4.3.2, обобщается на случай произвольного фиксированного d ^ 4, где й — размерность пространства.

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

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

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

Список публикаций по теме диссертации

[1] A.M. Райгородский, М.В. Титова, О дистанционных подграфах графов в пространствах малых размерностей, Современная математика и ее приложения, 20, 2011, 75-83. (A.M. РаЙгородскому принадлежит постановка задачи и редакция введения, М.В. Титовой принадлежит доказательство всех основных результатов.)

[2] А.Б. Купавский, A.M. Райгородский, М.В. Титова, О плотнейших множествах без расстояния единица в пространствах малых размерностей, Труды МФТИ, 4 (1), 2012, 111-121. (A.M. РаЙгородскому принадлежит постановка задачи о дистанционном числе Рамсея и редакция введения, A.B. Купавскому принадлежит постановка задачи о плотнейших множествах без расстояния единица и редакция истории задачи, М.В. Титовой принадлежит доказательство всех основных результатов.)

[3] А.Б. Купавский, М.В. Титова, Дистанционные числа Рамсея, Доклады Академии Наук, 449 (3), 2013, 267-270. (А.Б. Купавскому принадлежит редакция введения, доказательство утверждения о недистанционности графов, содержащих в качестве подграфа граф, изоморфный графу с (d/2+2) долями по три вершины. М.В. Титовой принадлежит доказательство всех основных результатов.)

[4] A. Kupavskii, A. Raigorodskii, М. Titova, New bounds for the distance Ramsey numbers, Discrete Mathematics, 313 (22), (2013), 2566-2574. (A.M. Райгородскому принадлежит доказательство верхней оценки дистанционного числа Рамсея, А.Б. Купавскому принадлежит редакция введения, доказательство утверждения о недистанционности графов, содержащих в качестве подграфа граф, изоморфный графу с (d/2+2) долями по три вершины. М.В. Титовой принадлежит доказательство всех основных результатов.)

[5] М.В. Титова, Задача о геометрических числах Рамсея, Фундаментальная и прикладная математика, 18 (1) (2013), 171-180.

Напечатано с готового оригинал-макета

Подписано в печать 01.11.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 341.

Издательство ООО "МАКС Пресс" Лицензия ИДЫ 00510 от01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

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

04201365771

Титова Мария Викторовна

КОМБИНАТОРНЫЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ В ЗАДАЧЕ О ГЕОМЕТРИЧЕСКИХ ЧИСЛАХ РАМСЕЯ

01.01.05 — теория вероятностей и математическая статистика 01.01.09 — дискретная математика и математическая кибернетика

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

Научный руководитель — д.ф.-м.н. А.М. Райгородский

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

Москва, 2013

Оглавление

Введение 4

Теория Рамсея..........................................................4

Комбинаторная и дискретная геометрия..............................7

Вероятностный метод..................................................9

1 История задачи и результаты 13

1.1 История задачи............................13

1.2 Формулировки результатов.....................16

2 Доказательства теорем 4-7 о нижних оценках дистанционного числа Рамсея в случаях плоскости и трехмерного пространства 20

2.1 Вспомогательные утверждения..................20

2.1.1 Вспомогательные утверждения для теорем 4 и 5.....20

2.1.2 Вспомогательные утверждения для теорем 6 и 7.....23

2.1.3 Локальная Лемма Ловаса..................23

2.2 Доказательство теоремы 4......................23

2.3 Доказательство теоремы 5......................26

2.4 Доказательство теоремы 6......................28

2.5 Доказательство теоремы 7......................29

2.6 Одномерный случай.........................30

3 Доказательство теоремы 8 об оценках дистанционного числа Рамсея в случаях малых размерностей пространства 32

3.1 Задача о плотнейших упаковках..................32

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

3.1.2 Определения из теории решеток и упаковок........34

3.1.3 Идеи получения нижних оценок 7П1(Мп)..........35

3.1.4 Основные результаты в задаче о плотнейших упаковках . 35

3.2 Конструкция Крофта для М2....................36

3.3 Конструкция для М3.........................37

3.4 Доказательство теоремы 15: результаты в задаче о плотнейших

множествах без расстояния единица................39

3.4.1 Доказательство теоремы 15 в случае п = 4........39

3.4.2 Доказательство теоремы 15 в случае п = 5........40

3.4.3 Доказательство теоремы 15 в случае п — 6........41

3.4.4 Доказательство теоремы 15 в случае п = 7........41

3.4.5 Доказательство теоремы 15 в случае п = 8........42

3.5 Доказательство теоремы 8......................43

4 Доказательство теоремы 9 об оценке дистанционного числа

Рамсея в случае растущей размерности пространства 44

4.1 Вспомогательная теорема об оценке сверху числа клик дистанционных графов ...........................44

4.2 Доказательство вспомогательной теоремы 16...........45

4.3 Доказательство основной теоремы 9 об оценке дистанционного числа Рамсея.............................47

4.3.1 Получение нижней оценки 5, с/)..........47

4.3.2 Доказательство теоремы 9 в случаях в, — 4, 5.......48

4.3.3 Доказательство теоремы 9 в случаях <1 ^ 6........54

Заключение 56

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

Введение

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

Теория Рамсея

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

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

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

Теория получила название в честь английского математика и философа Фрэнка Рамсея, предложившего ее фундаментальную идею, а также доказавшего результат, впоследствии ставший известным как теорема Рамсея (см. [73]). Теорема утверждает, что при любой раскраске ребер достаточно большого полного графа всегда найдется одноцветный полный подграф с наперед заданным числом вершин.

Начиная с 1930 годов теория Рамсея стала активно развиваться и обрела популярность благодаря работам знаменитого венгерского математика Пола

Эрдеша. Известные результаты теории Рамсея о геометрических и числовых множествах, ставшие стимулом ее дальнейшего развития, включают в себя теорему Эрдеша-Секереша о выпуклых многоугольниках (см. [37]), теорему Ван-дер-Вардена об арифметических прогрессиях (см. [86]), теорему Хэйлса-Джуита об игре в многомерные крестики-нолики (см. [47]), теорему Шура, а также множество ее обобщений, таких как теоремы Радо, Радо-Фолкмана-Сандерса, Хиндмана. Большой обзор по результатам теории Рамсея предоставлен в книге Грэхема, Ротшильда, Спенсера (см. [44]).

Одной из классических задач теории является задача о нахождении чисел Рамсея, которые возникают в формулировке теоремы Рамсея. В случае двух цветов утверждение теоремы состоит в том, что для любой пары целых чисел в, £ существует такое минимальное положительное целое число /¿(я, £), что в любом полном графе с Я(в, ¿) вершинами, ребра которого покрашены в синий и красный цвета, найдется либо полный подграф на 5 вершинах, у которого все ребра синие, либо полный подграф на £ вершинах, у которого все ребра красные. Если уйти от терминологии раскрасок, то классические числа Рамсея могут быть определены следующим образом: для данных £ N числом Рамсея ¿) называется такое минимальное натуральное число Я, что для любого графа С = (V, Е) на Я вершинах либо в С содержится й-вершинное независимое множество (т.е. множество вершин, свободное от ребер), либо в его дополнении б до полного графа К л на Я вершинах содержится вершинное независимое множество.

Точные значения Я(в, ¿) найдены для очень немногих й и £, в основном имеется очень большой зазор между верхними и нижними оценками, который не удается сократить даже в случаях маленьких й и Уже для в = t = 5 известно лишь, что 43 ^ Я(в^) ^ 49 (см. [39], [60], соответственно). Обзор результатов касательно маленьких параметров имеется в [43], таблицу последних лучших оценок классического числа Рамсея при малых можно посмотреть, например, в [70].

Верхняя оценка чисел Рамсея выводится из доказательства теоремы Рамсея, однако, когда Эрдсш и Секереш переоткрыли числа Рамсея, они предложили лучшую верхнюю оценку ([37], 1935 год):

(1)

что дает для диагонального случая (т.е. случая в = ¿) оценку

Я(5,5) < (1 + о(1)) —

Долгое время не удавалось существенно улучшить эту оценку, покуда в 1980 годы это не сделали Грэхем, Редль (см. [43]) и Томасон (см. [84]). Лучшую известную верхнюю оценку удалось получить Конлону в 2009 году (см. [16]):

R{s,s) < ■ 4S, 7 > 0. (2)

Для получения нижней оценки использовались различные нетривиальные методы. В 1947 году Эрдеш впервые применительно к задачам такого типа использует вероятностный подход — так называемую случайную раскраску (см. [32]), и получает нижнюю оценку для диагонального случая:

Д(Я,в)>-±=(1 + о(1))з2*.

В следующие 60 лет оценку удалось улучшить всего в два раза. Это было сделано в 1975 году Спенсером при помощи мощного вероятностного инструмента — Локальной Леммы Ловаса (см. [77], а также раздел «Вероятностный метод»). Таким образом, лучшей известной нижней оценкой диагонального числа Рамсея является следующая:

R(s,s) ^ ——(1 + o(l))s22. (3)

е

Из оценок недиагональных чисел Рамсея достаточно хорошие границы сверху и снизу известны для R(3, t). Нижнюю получил Ким ([54], 1995), верхнюю доказали Айтаи, Комлош и Семереди ([2], 1980):

Существуют также многочисленные обобщения чисел Рамсея. Например, изучаются многоцветные числа Рамсея, числа Рамсея для гиперграфов, индуцированные числа Рамсея, а также другие нетривиальные обобщения (см. [44]). Наиболее полные результаты исследований приведены в [69].

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

Комбинаторная и дискретная геометрия

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

В первую очередь интерес к задачам комбинаторной геометрии подняли многочисленные работы Пола Эрдеша. В 1935 году выходит статья Эрдеша-Секереша (см. [37]), решающая обобщение задачи Клейн о выпуклых четырехугольниках с помощью теории Рамсея (та самая статья, в которой Эрдеш и Секереш переоткрывают числа Рамсея). Задача, которую поставила и решила Клейн в 1934 году, звучала так: всегда ли среди пяти точек общего положения на плоскости найдется выпуклый четырехугольник?

Естественным обобщением этого стала гипотеза: существует ли такое число Л^(п), что среди любых N точек общего положения на плоскости найдется выпуклый п-угольник? Эрдеш и Секереш доказали, что М(п) конечно для всех п и выдвинули еще одну гипотезу: ЛГ(гг) = 2п~2 + 1. На данный момент известно, что 7У(гг) ^ 2п~2 +1 (см. [38]), и гипотеза проверена для п ^ 6 (см. [37], [62], [82]).

В работе 1946 года Эрдеш ставит вопросы о наибольшем числе единичных расстояний в множестве из п точек на плоскости (см. [24], [79]) и о числе различных расстояний (см. [14], [24], [45]), которые в числе прочих дают начало исследованиям различных свойств графов расстояний (см. раздел 1.1).

Следующие задачи стали ключевыми для образования и истории комбинаторной геометрии. Первая из них — это гипотеза Борсука о разбиении множеств на части меньшего диаметра (см. [12], [13], [72], [88], [95], [98], [99]. Речь идет о следующей задаче. Обозначим через /(п) минимальное количество частей меньшего диаметра, на которые можно разбить произвольное множество диаметра 1 в пространстве В 1933 году (см. [13]) Борсук высказал гипотезу, что /(п) = п + 1. Он доказал, что это верно для п ^ 2 и что /(п) ^ п 4-1. В течение долгого времени считалось, что гипотеза верна, и было получено много результатов, дающих на это надежду (см. [88], [95]). Однако в 1993 году гипотеза была неожиданно опровергнута Каном и Калаи (см. [52], [71])

во всех размерностях, начиная с п = 2015. На данный момент известно, что гипотеза верна при п ^ 3 (см. [95]) и неверна при п ^ 298 (см. [49]).

Вторая задача — это проблема Нелсона-Эрдеша-Хадвигера о раскраске метрических пространств. Задача была поставлена Нслсоном в 1950 году, а также независимо незадолго до этого похожая проблема изучалась Хадвиге-ром. Проблема формулируется так: необходимо найти хроматическое число равное минимальному количеству цветов, в которые можно так раскрасить все точки в евклидовом пространстве чтобы между одноцветными точками не было расстояния, равного единице:

х(Шс1)=тт{х:Ш<1 = У1и...11Ух |х-у|^1}.

Изучению величины х(^) посвящено множество работ (см., например, [1], [14], [55], [81], [95], [96], [100].

В то время как комбинаторная геометрия занимается комбинаторными свойствами геометрических объектов, дискретная геометрия изучает вопросы о взаимном расположении различных геометрических объектов в пространстве. Задачи этой дисциплины включают в себя проблемы упаковок и покрытий, замощений, раскрасок, разбиений и освещения (наиболее полные обзоры задач дискретной геометрии можно посмотреть в книгах [12], [14], [89], [93].

Источниками дискретной геометрии можно считать несколько течений, появившихся в начале XX века. Во-первых, в 1896 году выходит книга Мин-ковского «Геометрия чисел» (см. [61]), которая рассказывает о связях между теорией чисел и выпуклой геометрией. Дальнейшее развитие этой связи рассматривается в книгах Касселса «Введение в геометрию чисел» (см. [91]), Кокстера «Правильные многогранники» (см. [19]), Тота «Расположения на плоскости, шаре и пространстве» (см. [103]), и других. Одной из самых первых задач этой области считают также знаменитую «Задачу о саде» Сильвестра (см. [18], [80]). В задаче требовалось выяснить, верно ли, что среди любого конечного множества точек на плоскости, не лежащих на одной прямой, найдется такая пара точек, что проходящая через них прямая не содержит других точек данного множества.

Задача отыскания плотнейших упаковок является одной из наиболее значимых задач дискретной геометрии (см. [89], [91], [93]). Она ведет свое начало из знаменитой гипотезы Кеплера о плотнейшей упаковке шаров (которая рассматривалась Гильбертом как часть 18 проблемы, см. [48]). В середине прошлого века Тот и Роджерс используют новые комбинаторные подходы к классическим проблемам, поставленным Ньютоном, Гауссом, Минковским, Гильбертом и Туе. Тем самым они начинают развитие теории упаковок и

покрытий (см. [93]).

Задача о плотнейшей упаковке шаров звучит следующим образом. Пусть У{Х) — это объем множества X, 0) — п-мсрный шар радиуса г с центром в начале координат. Верхней плотностью множества X С Мп называется следующая величина:

У{ХПВ?{0))

6(Х) = Ит

г—»оо

У(В?( 0))

Множество X С называется упаковкой шаров, если представляет собой объединение непересекающихся открытых п-мерных шаров единичного радиуса. Задача Гильберта состояла в отыскании наибольшего значения величины <5(Х) (обозначим его А(п)), где X является упаковкой шаров. На данный момент она решена лишь для п < 3. Известны следующие асимптотические оценки максимума верхней плотности (нижнюю можно найти в [75], она следует из теоремы Минковского-Главки, верхняя — это известная граница Кабатянского-Левенштейна [90]):

-(1 + о(1))п ^ 1о§2 Д(п) ^ -(0.599 + о(1))п,

Задача о плотных упаковках шаров получила большое развитие, мотивированное приложениями экономичных упаковок в теории кодирования (передачи информации) и распознавании образов. Также большой интерес представляет изучение решетчатых упаковок, то есть таких упаковок X С Кп, у которых центры шаров из X образуют решетку в Мп. Такие упаковки исследованы лучше. Например, известны плотнейшие решетчатые упаковки в Кп, п ^ 8 (см. [93]).

Вероятностный метод

Вероятностный метод в комбинаторике возник в конце первой половины XX века. Первой работой, в которой эта техника была введена, считается работа Эрдеша 1947 года, где он приводит вероятностное доказательство нижней оценки числа Рамсея (см. [32]). Можно найти и более ранние работы, в которых уже использовался вероятностный способ получения результатов. Самые известные из них — работа Турана 1934 года (простое доказательство теоремы Харди-Рамануджана, см. [85]) и теорема Селе 1943 года о существовании турнира с большим количеством гамильтоновых путей (см. [83]). Однако именно Эрдеш начал активное развитие вероятностного метода как мощного инструмента для решения задач комбинаторики и экстремальной

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

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

Элементарный вероятностный метод, а именно простейший способ применения этой идеи, позволил получить Эрдешу упомянутую ранее первую нижнюю оценку числа Рамсея. Еще один пример известной задачи, где метод позволил получить неожиданно эффективный результат — это задача Эрдеша-Фюреди об остроугольных треугольниках (см. [29]). В работе был построен изящный и простой контрпример к гипотезе Данцера и Грюнбау-ма (см. [22]), державшейся 20 лет. Небольшое усовершенствование данного метода — мето�