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

• Титова, Мария Викторовна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Титова, Мария Викторовна

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение диссертации (часть автореферата) на тему «Комбинаторные и вероятностные методы в задаче о геометрических числах Рамсея»

Введение

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

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

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

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

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

Теория получила название в честь английского математика и философа Фрэнка Рамсея, предложившего ее фундаментальную идею, а также доказавшего результат, впоследствии ставший известным как теорема Рамсея (см. [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 лет. Небольшое усовершенствование данного метода — метод малых вариаций, — позволило получить простое доказательство классического результата комбинаторики и теории графов — теоремы Эрдсша о том, что существуют графы с наперед заданным хроматическим числом и обхватом (см. [26]). Речь идет о следующем вопросе: для данных целых положительных р, к, всегда ли существует граф с хроматическим числом не меньше к, содержащий только циклы длины не меньше д!

Вероятностных средств существует великое множество, и имеется большое количество книг, которые им посвящены (см., например, обзоры в [5], [105]). Мы сконцентрируем внимание на тех, которые помогли получить результаты данной работы.

Первое из них — это понятие случайного графа. Практически в одно и то же время независимо друг от друга это понятие определяют Гильберт (1959, [41]) и Эрдеш и Рсньи (1959, [33]). Эрдеш и Рсньи рассматривают две близких модели случайного графа, которые обозначаются С(п, М) и С(п, р). В обеих моделях случайный граф — это вероятностное пространство, в кото-

ром элементарными исходами являются графы без петель, кратных ребер и ориентации, имеющие п вершин. В первом случае графы имеют одинаковое фиксированное число ребер М, и вероятность каждого из этих графов полагается равной Во второй модели графы могут иметь различное число ребер, и каждое ребро графа возникает независимо от всех остальных ребер с вероятностью р. Таким образом, имеется пространство (fin, Тп, РПгР), где пространство элементарных исходов Пп — это множество всех графов без петель, кратных ребер и ориентации, которые можно построить на множестве вершин Vn ~ {1,..., п}, Тп — это сигма-алгебра всех подмножеств Qn, а

Рп,р(С?)=Р|£7|(1-Р)(5)"^> G = {Vn,E).

Исследованиям случайного графа в моделях Эрдеша—Реньи G(N,p) за последние десятилетия посвящено огромное количество работ (см. [5], [9], [10], [23], [51], [92], [102]). В частности, исследовались задачи о распределении малых подграфов в случайном графе (см. [7], [33], [67]), распределении количества деревьев (см. [8], [34]), о поиске гигантской компоненты и определении ее размера (см. [8], [58], [59]), о распределении диаметра случайного графа (см. [21], [50]), о моделях случайных геометрических графов (см. [68]). О приложении теории случайных графов к знаменитой проблеме Нелсона-Эрдеша-Хадвигера о раскраске пространств см. [97].

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

Еще одно вероятностное средство, которое мы используем, — это теорема, известная как Локальная Лемма Ловаса. Она является мощным инструментом комбинаторики и имеет многочисленные применения как в комбинаторике, так и в теории чисел и теоретической информатике. Теорема была впервые доказана в работе Эрдеша и Ловаса 1975 года (см. [31]). С тех пор было разработано несколько ее версий, самые известные из которых можно посмотреть в работах [36], [78]. Другие различные обобщения можно найти в книге [5]. Теорема имеет неконструктивный характер, однако существует и несколько ее алгоритмических версий (самые значительные последние результаты — [6], [63]).

Именно применение Локальной Леммы позволило Спенсеру улучшить нижнюю оценку классического числа Рамсея. Оценки, которые можно получить

с помощью явного построения (а не вероятностного способа), гораздо хуже.

Лучший известный результат, предложенный в 1981 году Франклом и У ил-

1 2

соном, дает нижнюю оценку s) > ехР(7(5)пл^)> гДе 7(s) х const. А для недиагонального случая R(s, 4) одна из лучших известных нижних оценок получена с помощью Локальной Леммы: R(s, 4) > s^+oU).

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

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

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

Результаты диссертации опубликованы в 5 работах автора [107]—[111].

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

Глава 1

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

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

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

Напомним, что дистанционным графом в д-мерном евклидовом пространстве называется граф С = (V, Е), в котором множество вершин составляют точки пространства М^ и для которого выполнено

У(х,у)€£ р(х,у) = а,

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

Заметим, что согласно данному определению, вершины, отстоящие друг от друга на расстояние 1, не обязательно соединены ребром.

В терминах дистанционных графов задача Эрдеша звучит следующим образом. Пусть дан дистанционный граф С = (V, Е) на плоскости. Чему равен максимум \Е\ при условии, что = п?

Также изучение свойств конечных дистанционных графов мотивировали классические проблемы Нелсона-Эрдеша-Хадвигера и Борсука (другие различные задачи, имеющие отношение к понятию дистанционного графа, см. в книге [14]). Дистанционные графы естественным образом связаны с понятием хроматического числа пространства. С одной стороны, для любого дистанционного графа С в М^ выполняется неравенство х(С) ^ гДе х{Н) — обычное хроматическое число графа. Напомним, что хроматическим числом графа называется минимальное количество цветов, требуемое для раскраски

его вершин, при которой любые вершины, соединенные ребром, раскрашены в разные цвета (см. [104]). С другой стороны, теорема Эрдеша-де Брейна (см. [15]) говорит о том, что если хроматическое число графа конечно, то оно достигается на некотором его конечном подграфе, т.е. х — х{Н) Для некоторого конечного дистанционного графа Н.

В 1959 году Эрдеш (см. [26]) доказал, что существуют графы со сколь угодно большим хроматическим числом и обхватом (длиной кратчайшего цикла). В 1976 году Эрдеш развил эту задачу, поставив вопрос (см. [28]): существует ли дистанционный граф на плоскости, имеющий хроматическое число 4 и не содержащий треугольников? Задача была решена уже три года спустя Уормалдом в [87]. В 2000 году О'Доннелл доказал существование графа расстояний на плоскости с хроматическим числом 4 и наперед заданным обхватом (см. [65], [66]). Результат интересен тем, что ни наличие треугольников, ни присутствие циклов какой-либо малой длины, как оказалось, не является необходимым для того, чтобы граф расстояний на плоскости имел максимальное известное хроматическое число.

Дистанционным графам посвящено множество работ (см. [14], [46], [81], [95]). Дистанционные графы часто связаны с теорией кодирования: рассматриваются дистанционные графы с вершинами из нулей и единиц, то есть графы, у которых множества вершин являются некоторыми сечениями пространства Хемминга (см., например, [35]). В последние несколько лет изучаются также случайные дистанционные графы (см. [102], [106]).

Подход к изучению свойств конечных дистанционных графов с точки зрения теории Рамсея был предложен в работе A.M. Райгородского (см. [101], а также обзор [111]), где было введено понятие дистанционного числа Рамсея ^neh(s,t,d) и получены нижние оценки. Нижний индекс был предложен в честь задачи Нелсона-Эрдеша-Хадвигера.

Определение 1. Дистанционным числом Рамсея R^¡EE{s,t,d) называется такое минимальное натуральное п € N, что для любого графа Gen вершинами верно следующее: либо он содержит индуцированный пос/граф на s вершинах, изоморфный некоторому дистанционному графу в либо его дополнение G до полного графа на п вершинах содержит индуцированный подграф на t вершинах, изоморфный некоторому дистанционному графу в Rd.

Далее везде мы рассматриваем только диагональный случай (т.е. s = t) с целью уменьшения громоздкости изложения.

Так как любое независимое множество может быть реализовано в про-

странстве любой размерности в качестве (пустого) дистанционного графа, то выполнено очевидное неравенство з, й) ^ 5). Из оценки Конлона

(см. введение, (1)) и этого неравенства получается верхняя оценка дистанционного числа Рамсея ^

Rmn(s,s,d) ^ 4s е~

YJnIs.

I 111 In

7 > 0.

Лучшая верхняя оценка была предложена A.M. Райгородским в работе [110].

Теорема 1 (Райгородский, [110]). Для 1 ^ d ^ s выполнено следующее неравенство:

Rner(s,s,d) < 2

~d < s s

2 [d/2] 5 [d/2]

< 4W2I

(1.1)

В работе [4] указывается также, что можно улучшить данную оценку:

RNEu{s,s,d) < R

5 s

[d/2] •> [d/2]

+ 2s.

Первые нижние оценки дистанционного числа Рамсея для растущего д были приведены в работе [101].

Теорема 2 (Райгородский, [101]). Выполняется следующее неравенство:

s s

U(®d)J 5

Теорема 3 (Райгородский, [101]). Пусть в —оо и ко = ко(в) такое, что

положим к\ = ко — 4. Тогда существует такая функция 5(5) = о(1) что если для некоторого п выполняется неравенство

то для всех d ^ к\ имеем

^neh(s,s,cO ^ п.

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

Следствие 1 (Райгородский, [101]). Положим т = в, й е П-

у/2

Ен(в,М) > —(1 + о(1))т21

4е

т

х(^)

в

. Для данных

(1.2)

Следствие 2 (Райгородский, [101]). Пусть (I = 0(1пв). Существует такая константа 7 > 0, что выполняется следующее неравенство:

Преимущества этих двух оценок зависят от асимптотического роста ¿(з). При сI = о(1п 1п в) оценка следствия 1 сильней оценки следствия 2, т.к.

В случае же 1п1пй = о ((Г), аналогичные неравенства показывают превосходство оценки следствия 2.

Следствие 1 вытекает из теоремы 2 согласно оценке классического числа Рамсея, полученной при помощи Локальной Леммы Ловаса. Следствие 2 получено из теоремы при помощи технических вычислений, а доказательство самой теоремы 3 использует вероятностный подход, который включает в себя мартингальную технику (см. [5]).

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

Список литературы диссертационного исследования кандидат наук Титова, Мария Викторовна, 2013 год

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

[1] P.K. Agarwal, J. Pach, Combinatorial Geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, 1995.

[2] M. Ajtai, J. Komlos, E. Szemeredi, A note on Ramsey numbers, J. Combin. Theory Ser., 29 (3), 1980, 354-360.

[3] N. Alon, M. Krivclevich, Extremal and Probabilistic Combinatorics, 2006.

[4] N. Alon, A. Kupavskii, Two notions of unit distance graphs, to be submitted.

[5] N. Alon, J.H. Spencer, The probabilistic method, 2nd ed., John Wiley and Sons, New York, 2000.

[6] J. Beck, An Algorithmic Approach to the Lovasz Local Lemma, I, Random Structures and Algorithms, 2, 1991, 343-366.

[7] B. Bollobäs, Threshold functions for small subgraphs, Math. Proc. Camb. Phil. Soc., 90, 1981, 197-206.

[8] B. Bollobäs, The evolution of random graphs, Trans. Amer. Math. Soc., 286, 1984, 257-274.

[9] B. Bollobäs, Martingales, isoperimetric inequalities and random graphs, Combinatorics (Eger 1987), Colloq. Math. Soc. Jänos Bolyai, 52, North-Holland, Amsterdam, 1988, 113-139.

[10] B. Bollobäs, Random Graphs, 2nd ed., Cambridge Univ. Press, 2001.

[11] B. Bollobäs, O.M. Riordan, Mathematical results on scale-free random graphs. Handbook of graphs and networks, Wiley-VCH, Weinheim, 2003, 134.

[12] V.G. Boltyanski, H. Martini, P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997.

[13] K. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundamenta Math., 20, 1933, 177-190.

[14] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, New York, 2005.

[15] N.G. de Bruijn, P. Erdos, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (5), 1951, 371-373.

[16] D. Conlon, A new upper bound for diagonal Ramsey numbers, Annals of Mathematics, 170, 2009, 941-960.

[17] D. Coulson, A 15-colouring of 3-space omitting distance one, Discrete Math., 256, 2002, 83-90.

[18] H.S.M. Coxeter, A problem of collinear points, Amer. Math. Monthly 55, 1948, 26-28.

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

[20] H.T. Croft, Incident incidents, Eureka, Cambridge, 30, 1967, 22-26.

[21] R. Damerell, On Moore graphs, Math. Proc. Camb. Phil. Soc., 74, 1973, 227236.

[22] L. Danzer, B. Grünbaum, Uber zwei Probleme bezüglich konvexer Körper von P. Erdos und von V.L. Klee, Mathematische Zeitschrift, 79, 1962, 95-99.

[23] R. Durrett, Random Graph Dynamics, Cambridge Univ. Press, 2006.

[24] P. Erdos, On a set of distances of n points, Amer. Math. Monthly, 53, 1946, 248-250.

[25] P. Erdos, Some Remarks on the Theory of Graphs, Bulletin of the American Mathematical Society, 53, 1947, 292-294.

[26] P. Erdos, Graph theory and probability, Canad. J. Math., 11, 1959, 34-38.

[27] P. Erdo's, On extremal problems of graphs and generalized graphs, Israel Journal of Mathematics, 2 (3), 1964, 183-190.

[28] P. Erdos, Unsolved Problems, Proc. Fifth Brit. Comb. Conf. (Univ. Aberdeen, Aberdeen, 1975), Util. Math. Publ., Winnipeg, 1976.

[29] P. Erdos, Z. Füredi, The greatest angle among n points in the d-dimensional Euclidean space, Annals of Discrete Math., 17, 1983, 275-283.

[30] P. Erdos, D.J. Kleitman, B.L. Rothschild, Asymptotic enumeration of Kn-free graphs, International Colloquium on Combinatorial Theory, Atti dei Convegni Lincei, 17 (2), Rome, 1976, 19-27.

P. Erdos, L. Lovasz, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and Finite Sets, II, Colloq. Math. Soc. Janos Bolyai, 10, North-Holland, Amsterdam, 1975, 609-627.

P. Erdos, Some Remarks on the Theory of Graphs, Bulletin of the American Mathematical Society, 53, 1947, 292-294.

P. Erdos, A. Renyi, On random graphs, I, Publ. Math. Debrecen, 6, 1959, 290-297.

P. Erdos, A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5, 1960, 17-61.

P. Erdos, C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7, 1962.

P. Erdos, J.H. Spencer, Lopsided Lovasz local lemma and latin transversals, Discrete Appl. Math., 30, 1991, 151-154.

P. Erdos, G. Szekeres, A combinatorial problem in geometry, Compositio Math., 2, 1935, 463-470.

P. Erdos, G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest., Eotvos Sect. Math., 3-4, 1961, 53-62.

G. Exoo, A Lower Bound for R(5,5), J. Graph Th., 13, 1989, 97-98.

F.M. de 01. Filho, F. Vallentin, Fourier analysis, linear programming, and densities of distance avoiding sets in Rn, Eur. Math. Soc., 12, 2010, 14171428.

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

A.M. Gleason, R.E. Greenwood, Combinatorial Relations and Chromatic Graphs, Canadian Journal of Mathematics, 7, 1955, 1-7.

R. L. Graham, V. Rodl, Numbers in ramsey theory, Surveys in Combinatorics, London Math. Soc. Lecture Note Series no. 123, Cambridge Univ. Press, London, 1987, 111-153.

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

L. Guth, N.H. Katz, On the Erdos distinct distance problem in the plane, Preprint http://arxiv.org/abs/1011.4105, 2010.

H. Hadwiger, Ein Uberdeckungssatz fur den Euklidischen Raum, Portugaliae Math., 4, 1944, 140-144.

A.W. Hales, R.I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc., 106, 1963, 222-229.

D. Hilbert, Mathematische Probleme, Archiv. Math. Phys., 1, 1901, 44-63.

A. Hinrichs, Spherical codes and Borsuk's conjecture, Discr. Math., 243, 2002, 253-256.

A. Hoffman, R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Der., 4, 1960, 497-504.

S. Janson, T. Luczak, A. Ruciriski, Random graphs, Wiley, NY, 2000.

J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 29 (1), 1933, 60-62.

G. Kery, On a Theorem of Ramsey (in Hungarian), Matematikai Lapok, 15, 1964, 204-224.

J.H. Kim, The Ramsey number R(3,t) has order of magnitude t2/logi, Random Structures and Algorithms, 7, 1995, 173-207.

V. Klec, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991.

A.A. Kokotkin, A.M. Raigorodskii, On large subgraphs of distance graphs having small chromatic number, Abstracts of the talks at the international conference «Fete of combinatorics and computer science», Keszthely, Hungary, August, 2008.

D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19, 1972, 1-24.

T. Luczak, Component behavior near the critical points of the random graph process, Random Structures and Algorithms, 1, 1990, 287-310.

[59] T. Luczak, B. Pittcl, J. Wicrman, The structure of a random graph near the point of the phase transition, Trans. Amer. Math. Soc., 341, 1994, 721-748.

[60] B.D. McKay, S.P. Radziszowski, R(4,5)=25, J. Graph., 19, 1995, 309-322.

[61] H. Minkowski, Geometrie der Zahlen, RG Teubncr, Leipzig-Berlin, 1953.

[62] W. Morris, V. Soltan, The Erdos-Szekeres problem on points in convex position - a survey, Bull. Amer. Math. Soc., 37, 2000, 437-458.

[63] R. Moser, G. Tardos, A constructive proof of the general Lovasz local lemma, Journal of the ACM, 2010.

[64] O. Nechushtan, On the space chromatic number, Discrete Math., 256, 2002, 499-507.

[65] P. O'Donncll, Arbitrary girth, 4~chromatic unit distance graphs in the plane

I. Graph embedding, Geombinatorics, 9, 2000, 180-193.

[66] P. O'Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane

II. Graph description, Geombinatorics, 9, 2000, 145-152.

[67] Z. Palka, On the number of vertices of given degree in a random graph, J. Graph Theory, 4, 1982.

[68] M. Penrose, Random Geometric Graphs, Oxford Studies in Probability, 5, 2003.

[69] S.P. Radziszowski, Small Ramsey Numbers, Electronic J. Combinatorics Dynamical Survey DS1, Jul. 4, 2004, 1-42.

[70] S.P. Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey 1, revision 13, 2011.

[71] A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Mathematical Society. Lecture Note Series, 347, 2007, 202-248.

[72] A.M. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, 2013.

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

[74] V. Rôdl, On a packing and covering problem, Eur. J. Combinatorics, 6, 1985, 69-78.

[75] W.M. Schmidt, On the Minkowski-Hlawka theorem, Illinois J. Math., 7 (18), 1963, 18-23.

[76 [77

[78

[79

[80 [81

[82 [83 [84 [85 [86 [87

[88 [89

J. Shearer, On a problem of Spencer, Combinatorica, 5 (3), 1985, 241-245.

J. Spencer, Ramsey's theorem — A new lower bound, J. Comb. Theory (A), 18, 1975, 108-115.

J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Mathematics, 20, 1977, 69-76.

J. Spencer, E. Szemeredi, W.T. Trotter, Unit distances in the Euclidean plane, Graph Theory and Combinatorics, B. Bollobas, Academic Press, London, 1984, 293-303.

J.J. Sylvester, Mathematical Question 11851, Educational Times, 59, 1893, 98.

L.A. Szekely, Erdos on unit distances and the Szemeredi-Trotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11, 2002, 649-666.

G. Szekeres, L. Peters, Computer solution to the 17-point Erdos-Szekeres problem, ANZIAM J., 48, 2006, 151-164.

T. Szele, Kombinatorikai Vizsgalatok az Iranyitott Teljes Grdffal Kapcsolatban, Mat. Fiz. Lapok, 50, 1943, 223-256.

A. Thomason, An upper bound for some ramsey numbers, J. Graph Theory, 12, 1988, 509-517.

P. Turan, On a theorem of Hardy and Ramanujan, Journal of the London Mathematical Society, 9, 1934, 274-276.

B.L. Van der Wacrdcn, Beweis einer Baudetschen Vermutung., Nieuw Arch. Wisk., 1927, 15, 212-216.

N. Wormald, A 4-Chromatic Graph With a Special Plane Drawing, Australian Mathematics Society (Series A), 28, 1979, 1-8.

В.Г. Болтянский, И.Ц. Гохберг, Теоремы и задачи комбинаторной геометрии, Москва, Наука, 1965.

П.М. Грубер, К.Г. Лекксркеркер, Геометрия чисел, Москва, Наука, 2008.

[90] Г.А. Кабатянский, В.И. Левенштейн, О границах для упаковок на сфере и в пространстве, Пробл. передачи информ., 14 (1), 1978, 3-25.

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

[92] В. Ф. Колчин, Случайные графы, Физматлит, Москва, 2002.

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

[94] К.А. Михайлов, A.M. Райгородский, О числах Рамсея для полных дистанционных графов с вершинами в {0,1}п, Матсм. сб., 200 (12), 2009, 63-80.

[95] A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи матем. наук, 56 (1), 2001, 107-146.

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

[97] A.M. Райгородский, Раскраски пространств и случайные графы, Фундаментальная и прикладная математика, 11 (6), 2005, 131-141.

[98] A.M. Райгородский, Проблема Борсука, Москва, МЦНМО, 2006.

[99] A.M. Райгородский, Вокруг гипотезы Борсука, СМФН, 23, 2007, 147-164.

[100] А. М. Райгородский, Линейно-алгебраический метод в комбинаторике, МЦНМО, Москва, 2007.

[101] A.M. Райгородский, Об одной серии задач рамсеевского типа в комбинаторной геометрии, Доклады РАН, 413 (2), 2007, 171-173.

[102] A.M. Райгородский, Модели случайных графов, МЦНМО, Москва, 2011.

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

[104] Ф. Харари, Теория графов, Москва, Мир, 1973.

[105] П. Эрдеш, Дж. Спенсер, Вероятностные методы в комбинаторике, Москва, Мир, 1976.

[106] А.Р. Ярмухаметов, Гигантская и мелкие компоненты в случайных дистанционных графах специального вида, Математические заметки, 6 (92), 2012, 949-953.

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

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

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

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

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