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

• Бобу Андрей Викторович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Бобу Андрей Викторович

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

3.3.1 План доказательства

3.3.2 Этап 1: построение совокупности М

3.3.3 Этап 2: линейно-алгебраический метод

3.3.4 Этап 3: завершение доказательства

Заключение

Список условных обозначений

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

Введение

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

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

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

Во второй половине прошлого века начала активно развиваться область комбинаторики, связанная с изучением экстремальных свойств совокупностей конечных множеств с определенными запретами на пересечения. Развитие в этой области математики было связано в первую очередь с переоткрытием пионерского результата Эрдеша, Ко и Радо (см. [1]). Еще в 1938 году авторы этой работы установили следующий факт. Обозначим/(п, к, £) максимально возможную мощность семейства к-элемептпых подмножеств множества = {1,..., п}, попарно пересекающихся не менее, чем по £ элементам. Тогда при п ^ по(к,£)

/ (п,м) = СП—

При этом оценка снизу в данном равенстве практически очевидна, ее дает пример тривиальной конструкции множеств, которые содержат некоторые фиксированные £ элементов. В 1977 года Франкл показал, что п0(к,£) = (к — £ + 1)(£ + 1) при £ ^ 15 (см. [2]), а в 1984 году Уилсон доказал, что формула для п0(к,£) справедлива и при £ < 15 (см. [3]). Однако оставалось невыясненным, что же происходит при п < п0(к, £). Но в 1996 работа Алсведе и Хачатряна дала окончательный ответ на поставленный вопрос и было найдено точное значение величины /(п, к, £) при всех значениях параметров п, к £

по себе довольно проста (хоть и не совпадает с тривиальной конструкцией Эрдеши Ко Ридо). а вот доказательство ее оптимальности весьма нетривиально.

Одновременно с этим активно изучались смежные вопросы (см. обзор [6]). Например, как изменится ситуация, если исключить из рассмотрения тривиальную конструкцию Эрдеши Ко Ридо (см. [7], [8])? Другое важное обоб-

щение связано со снятием ограничения на мощность исследуемых множеств (см. [9]-[12]). Наконец, значительное количество работ посвящено ситуации, когда не менее в множеств попарно пересекаются хотя бы по Ь элементам (см. [13]—[16]). Изучаются и другие смежные проблемы (см. [17]-[24]).

Данную задачу можно сформулировать на языке теории гиперграфов. Напомним, что гиперграфом называется пара Н = (V, Е), где V — некоторое конечное множество, а Е — совокупность подмножеств множества V. Множество V обычно называют множеством вершин, а совокупность Е — множе-

к

дом ребре содержится ровно к вершин. В таком случае ](п, к,Ь) есть макси-

кп любые два ребра пересекаются не менее, чем по ¿элементам, 0 ^ Ь < к < п:

/(п,к,Ь) = тах{т: ЗН = (V, Е), IV| = п, |Е| = т, V А е Е |А| = к,

V А, В е Е |А П В| ^ ¿}.

Прямо противоположная ситуация — ограничение на максимальную мощность пересечения ребер — приводит нас к теории кодирования. Задача состоит в отыскании величины ^(п, к, ¿) — максимального числа ребер в к-

п

каются не более, чем по ¿элементам, 0 ^ Ь < к < п:

й(п,М) = тах{т: ЗН = (V, Е), IV| = п, |Е| = т, V А е Е |А| = к,

VА, В е Е |А П В| < ¿}.

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

к

к

мощность пересечения ребер величиной Ь означает, что попарные хэмминго-вы расстояния между кодовыми словами не меньше 2(к — ¿). Тем самым мы приходим к широко известной задаче о кодах, исправляющих ошибки, и работа над этой проблемой все еще далека от завершения. Довольно простая нижняя оценка величины ^(п, к, ¿) была получена еще в 1950-е годы Р. Вар-шамовым и Е. Гилбертом (см. [25], [26]). Что же касается верхних оценок, то здесь имеется целый ряд блестящих результатов, среди которых можно отметить границы Хэмминга (см. [27]), Элайеса-Бассалыго (см. [28]), оценки Левенштейна (см. [29]) и границу линейного программирования (см. [30]). Подробный обзор можно найти в книге [31].

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

кп могут пересекаться по £ элементам, 0 ^ £ < к < п:

т(п, к, £) = тах{т: ЗЯ = (V, Е), | = п, |Е| = т, V А е Е |А| = к,

V А, В е Е |А П В| = £}?

Первые статьи по этой проблеме появились в 1970-х годах и касались отдель-

к£

случая Эрдеш предположил (см. [35]), что при к ^ 4, начиная с некоторого по = по(к,£),

т(п,к,£) ^ тах |СП—?—},Сп| . В 1980 Франкл доказал (см. [36]), что при к ^ 3£ + 2 и п ^ то

т(п, к, £) ^ (1 + о(1))СП—1—1.

А в 1981 году Франкл и Уилсон показали, что при определенных ограни-

( к — £)

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

к£

п ^ то Наиболее изучен случай, когда к и £ — константы, не зависящие от п

когда к ~ к'п,£ ~ £'п, где к' и £' — положительные константы, не завися-п

иптереспая ситуация, когда к = п/2, а £ = О (д/п)? она приводит к графам, схожим с кпезеровскими, и изучается в работах [58]-[60].

Конечно, у этой задачи появились и обобщения, довольно популярным является вопрос о целом множестве запрещенных пересечений. Среди большого количества работ, посвященных данной проблеме, мы можем выделить как классические исследования [37], [61]—[63], так и относительно недавние работы [64]—[66]. Отметим, что в работе [64] изучался случай, когда запрещен целый диапазон пересечений. Среди большого разнообразия случаев мы выделим задачу оценивания величины р(п, к, £1, £2) — максимального числа

кп секаются не менее, чем по ¿1 элементам, и не более, чем по ¿2 элементам, 0 ^ ¿1 ^ ¿2 ^ к < п:

р(п,к,Ь1,Ь2) = тах{т: ЗН = (V, Е), IV| = п, |Е| = т, V А е Е

|А| = к, VА, В е Е ¿1 < |А П В| < ¿2}.

Иными словами, мы разрешаем ребрам гиперграфа пересекаться по любому числу вершин из отрезка [¿1, ¿2].

Исследование величин т(п,к,Ь) и р(п,к,Ь1,Ь2) было в значительной степени мотивировано задачами комбинаторной геометрии. Величина т(п, к, ¿) оказалась напрямую связана с задачей Нельсона Эрдеши Хидвигери о хроматическом числе пространства, ставшей широко известной в 50-е годы XX столетия (см. [50], [67]-[69]). Она заключается в отыскании величины х(Кп), называемой хроматическим числом пространства и равной минимальному числу цветов, в которые можно так покрасить все точки Кп, чтобы никакие две точки одного цвета не находились на расстоянии 1. Эта проблема до сих пор является открытой даже для случая евклидовой плоскости: известно лишь, что 5 ^ х(^2) ^ 7. Для обоснования более слабой нижней оценки х(К2) ^ 4 достаточно указать пример Мозеровского веретена (см. [70]) — довольно простого графа единичных расстояний, то есть графа с вершинами в точках плоскости, которые соединены ребром в том и только том случае, если расстояние между ними равно 1. Также при помощи явной раскраски легко показать, что х(К2) ^ 7, и долгое время в этой задаче ничего больше не было известно. Однако совсем недавно произошел удивительный прорыв: в 2018 году в работе [71] Обри де Грей привел пример графа единичных расстояний на плоскости, который нельзя покрасить в 4 цвета. Возможно, в дальнейшем удастся упростить приведенный им пример или даже отыскать подобный граф, который не красится и в 5 цветов.

Однако при больших п зазор становится только больше, уже для п = 3 известно лишь, что 6 ^ х(^3) ^ 15 (см. [72], [73]). О других малых значе-п

результатом в общем случае была теорема Райского, доказанная в 1970 году

п

х(Кп). Большое продвижение в случае растущего п связано в первую очередь с упоминавшейся выше работой [33] Лармана и Роджерса 1972 года. В данной работе исследовалась величина т(п, 3,1), для которой была доказана п

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

Х(^п) < (3 + о(1))п, п — то.

Однако довольно длительное время вообще не было известно, растет лих(^п) экспоненциально. Ответ на этот вопрос дала та самая работа Франкла и Уил-

т(п, к, £)

Х(^п) ^ (1.207... + о(1))п, п —у то.

Наилучшая нижняя оценка при п — то была получена не так давно в работе [50] и выглядит следующим образом:

Х(^п) ^ (1.239 ... + о(1))п, п — то.

Разумеется, задача обросла большим количеством обобщений и переформулировок, в частности, указанная проблема имеет смысл для произвольных метрических пространств (см. [53], [80]). Нельзя обойти вниманием и задачу о хроматическом числе сферы х(^п), которая формулируется ровно так же, как проблема Нельсона Эрдеши Хидвигери. только вместо всего прострин-

п

из наиболее естественных сопутствующих вопросов звучит следующим образом: что будет, если запретить несколько расстояний? Иными словами, чему равно минимальное количество цветов х(^П /1,... /то), в которые можно так покрасить точки пространства, чтобы расстояние между любыми двумя точками одного цвета не лежало в множестве {/1,..., /то} (см. работы [50], [65], [66], [75], [86])? Можно рассматривать ситуацию, когда запрещаются более сложные точечные конфигурации. Примером служит хроматическое число пространства без одноцветных симплексов Хд(^п) (см. [87]-[88]).

Нас будет в первую очередь интересовать запрет одноцветных треугольников. А именно, для 0 < а < 1 < Ь < л/2 определим вели чипу ха,ь (^п) как минимальное количество цветов, в которые можно так покрасить точки пространства чтобы никакие три точки не образовывали равнобедренный треугольник с длинами боковых сторон 1 и длиной основания в пределах от а до Ь. Данную величину называют хроматическим числом пространства с запрещенными одноцветными треугольниками. Она активно изучалась в недавних работах [89]—[92]. Заметим, что можно указать довольно тривиальную верхнюю оценку исследуемой величины:

ХаАЮ ^ Х(^) ^ (3 + 0(1))п, п —то.

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

Цель работы и основные задачи

Цель настоящей работы состоит в получении новых нижних и верхних оценок величин т(п,к,£) и р(п, к, ¿1, ¿2) и применении полученных результатов к задачам теории кодирования и комбинаторной геометрии, в частности, к оценкам хроматических чисел пространства с запрещенными одноцветными треугольниками.

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

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

Теоретическая и практическая ценность полученных результатов

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

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

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

Основные положения диссертации, выносимые на защиту

1. Получены новые нижние оценки величины m(n, k, t) в ситуации, когда k ~ k'n, t ~ t'n при n ^ то, a fc; £ (0,1) t' £ (0, k') — фиксированные константы.

2. Получены новые оценки величины p(n, k, ti, t2) для различных ситуаций относительно параметров n, k, t1, t2.

3. На основании оценок из пунктов 1 и 2 получены верхние оценки классической в теории кодирования величины A(n, 2£, w) — максимального числа двоичных векторов длины n, теса w, находящихся друг от друга на хэмминговом расстоянии не менее 2£.

4. Получены новые нижние оценки хроматического числа пространства с запрещенными одноцветными треугольниками.

Степень достоверности и аппробация результатов

Все результаты работы строго доказаны.

По теме диссертации были сделаны доклады на следующих научных семинарах:

— Кафедральный научно-исследовательский семинар кафедры дискретной математики ФИВТ МФТИ под руководством профессора A.M. Ри¡iгородского (2017 г.)

— Научный семинар по теории кодирования в ИППИ им. Харкевича под руководством д. ф.-м.н. Л. А. Бассалыго (2017 г.)

Публикации

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

— в работах [97] и [98] доказаны нижние оценки величины m(n, k, t) при n ^ то;

— в работах [99] и [100] доказаны нижние и верхние оценки величины р(п, к, ¿1, ¿2), получено следствие для задачи о равновесных кодах, исправляющих ошибки;

— в работе [101] доказана теорема о нижней оценке хроматического числа пространства с запрещенными одноцветными треугольниками.

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

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

Настоящая работа состоит из трех глав.

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

< к. Во второй части для случая ^ к при помощи методов комбинаторики и идей теории кодирования нами будут получены новые нижние границы величины т(п, к,^). Наконец, мы приведем новую границу объема равновесного кода, исправляющего ошибки, при помощи оценок величины т(п, к, ¿) и методов теории графов.

Во второй главе речь пойдет о величине р(п, к, ¿1, ¿2). Сначала мы коснемся имеющихся на настоящий момент оценок и установим соотношение между ними. Затем, используя границы теории кодирования и обобщение линейно-алгебраического метода, мы докажем новые верхние и нижние границы величины р(п, к, ¿1, ¿2). При помощи простых комбинаторных соображений и перебора небольшого количества вариантов мы установим точное значение р(п, к, ¿1, ¿2) Для некоторых значений параметров. В заключительной части мы получим еще одну границу для кодов, исправляющих ошибки, и покажем, что в ряде случаев она численно совпадает с наилучшей известной на настоящий момент границей Левенштейна.

Третья глава касается хроматических чисел пространства с запрещенными одноцветными треугольниками ха,ъ(Мп). Мы продемонстрируем, как величина р(п, к, ¿1, ¿2) связана с ха,ъ(Жп)- Затем мы введем некоторый аналог р(п, к, ¿1, ¿2), который позволит в некоторых ситуациях улучшить оценки предыдущих исследователей, и приведем наглядное сравнение новых оценок и имеющихся на настоящий момент результатов.

Гл яв ^^

Оценки величины т(п, к,

Данная глава посвящена оценкам величины т(п, к, £), определяемой как максимальное число ребер в к-однородпом гиперграфе па п вершинах, у которого любые два ребра не могут пересекаться по ¿элемента м, 0 ^ £ < к < п:

т(п,М) = шах{т: ЗЯ = (V, Е), IV| = п, |Е| = т, V А е Е |А| = к,

VА, В е Е |А П В| = ¿}.

Основными результатами данной главы являются теорема 5, которая показывает, что теорема Франкла-Уилсона асимптотически точна в случае 2^ < к, теоремы 6, 8 и 9, которые дают новые нижние оценки величины т(п, к, ¿) в случае 2£ ^ к, а также теорема 10, дающая новую границу в теории кодирования. Данные результаты были сформулированы и доказаны в работе [97].

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

Напомним также определения величин ](п, к, ¿) и ^(п, к, ¿):

/(п, к, ¿) = шах{т: ЗЯ = (V, Е), IV| = п, |Е| = т, V А е Е |А| = к,

V А, В е Е |А П В| ^ ¿};

^(п, к, ¿) = шах{т: ЗЯ = (V, Е), IV| = п, |Е| = т, V А е Е |А| = к,

VА, В е Е |А П В| < ¿}.

Сперва обсудим верхние оценки величины т(п, к,^). В связи с этим приведем упоминавшуюся выше классическую теорему Франкла и Уилсона.

Теорема 1. Пусть £ = к — д, где д — степень простого числа. Тогда имеют место два случая:

1. если 2£ < к, то

9—1

т(п,к,£) < ^ СП;

¿=0

если 2£ ^ к, то при, ^ = к — 2д + 1 = 2£ — к + 1

С ^

т(п,к,£) < с|

Если при п ^ то числа к и £ достаточно малы в сравнении с га, то в рамках своих предположений теорема 1 асимптотически точна. Однако в прямо противоположной ситуации все намного сложнее. А именно, совсем недавно в работах [51], [52] была доказана следующая теорема.

Теорема 2. Пусть к < |7 2£ ^ к и £ = к — д, где д — степень простого числа. Положим й = 2£ — к + 1. Пусть, да лее, ^, ¿2 € N таковы, что + ¿2 = ¿.Положим п1 = п — ¿1; к1 = к — ¿ь Определим натуральное число г из соотношения

(к1 — ¿2 + 1)^2 + < П1 < (к1 — ¿2 + 1^2 + .

Тогда,

т(п, к, £) <

С ^2+2г с

С ^2+г с г с Ск1 Сп1—к1

Конечно, неочевидно, что двойное неравенство в формулировке теоремы 2

г

элементарными преобразованиями легко получить следующее неравенство:

(¿2 + 1)(к1 — ¿2 + 1) 1 < (¿2 + 1)(к1 — ¿2 + 1) п1 — 2к1 + 2^2 — 2 < г < п1 — 2к1 + 2^2 — 2 .

г

■ (¿2 + 1)(к1 — ¿2 + 1)

г=

п1 — 2к1 + 2^2 — 2

1

Видно, что теорема 2 касается случая 2 теоремы 1. В работах [51], [52] показано, что теорема 2 значительно уточняет оценку из случая 2 теоремы 1 в

классе ситуаций, который носит название "асимптотического" и который мы сейчас опишем. Итак, пусть даны числа к' е (0,1), £' е (0,к'). Пусть, далее, к ~ к'п, £ ~ £'п при п ^ то. С учетом формулы Стирлинга (см. [93]) нетрудно убедиться в том, что в указанных предположениях все интересующие нас оценки имеют вид (с + о(1))п, где с > 1 — константа, т.е. их логарифмы асимптотически равны п 1п с. Мы скажем, что две оценки разнятся значи-

с

асимптотически совпадающими. Оказалось (см. [51]), что при 2£ ^ к оценки из теоремы 2 значительно сильнее оценок Франкла-Уилсона.

Перейдем к нижним оценкам величины т(п, к,£). Мы уже упоминали выше о величине /(п, к,£) и о том, что задача по ее поиску полностью решена в работе [4]. Сама работа весьма сложна, однако конструкция, на которой достигается максимум этой величины, устроена довольно просто. А именно, зафиксируем натуральное число 0 ^ г ^ к — £. Возьмем произвольное множество элементов мощности £ + 2г (обозначим его А) и в качестве ребер гипер-

кА £ + г элементам. Очевидно, что все они уже внутри А пересекаются как минимум по £ элементам, что и требуется. Мы будем называть так построенные множества ребер гиперграфа конструкциями Алсведе-Хачатрянас параметрами к, £ и г. Если же множества пересекаются с А ровно по £ + г элементам, мы будем говорить об упрощенной конструкции Алсведе-Хачатряна.

Следующая теорема (именно она доказана в работе [4]) указывает, чему равна величина /(п, к,£) и при каком г она достигается.

Теорема 3. Пусть 2к — £ ^ п и для некоторого г е N и {0}

(к — £ + 1'(2 + г—г) ^ п< (к — £ + 1)(2 + ,

причем при г = 0 формально полагаем, что-= то. Тогда

г

шт{2г,к— Ь}

чк—Ь—г 'и-Ь-2г.

/(п, к,£) = ^ СЬ+2гСП

Сразу отметим, что элементарными преобразованиями неравенство на па-г

' (£ — 1)(к — £ + 1)

г = < п — 2к + 2£ — 2 0, £ = 0, 1

, если £ > 1, ,

, (1-1)

Наконец, нам потребуется теорема из теории кодирования, которая будет касаться величины h(n, k, t). Она впервые приведена в работе [29] и является частным случаем границы Виршишжи Гилберта для равновесных кодов.

Теорема 4. Пусть 2k — t ^ n. Тогда

с k

h(n, k, t) ^ —--n-. (1.2)

Erii rik—i Ck Cn—k

i=t+1

Теоремы Алсведе-Хачатряна и Варшамова-Гилберта дают нижние оценки в нашей задаче, поскольку

m(n,k,t) ^ f(n,k,t + 1); (1.3)

m(n, k, t) ^ h(n, k, t — 1).

В разделе 1.3 мы покажем, что оценка (1.3) асимптотически точна при 2t < k. А для случая 2t ^ k ниже мы приводим рисунки, из которых видно, как соотносятся эти оценки с верхней границей из теоремы 2. На обоих рисунках по горизонтали откладывается t' в пределах от ^ до k'. По вертикали откладывается величина lnbnund, где "bound" — это либо нижняя оценка из теорем 3 и 4 (они названы "АХ" и "VG" в честь своих авторов), либо верхняя оценка из теоремы 2 (она обозначена "Upper"). На первом рисунке изображен случай k' = 0.5, на втором — случай k' = 0.1. Видно, что при t', расположенных ближе к kr, все довольно хорошо за счет теоремы 3, а ближе к правой границе интервала значений t' выигрывает теорема 4. Это является довольно ожидаемым, и хочется улучшить оценку в середине интервала. В следующем разделе мы попытаемся в некотором смысле "склеить" конструкции, дающие оценки из теорем 3 и 4.

1.2 Формулировки основных теорем и численные результаты

2t < k

Теорема 5. Пусть k = k'n,t = t'n при n ^ то и 2t < k. Тогда оценка

min{2r,k— t—1)}

m(n, k, t) ^ f (n, k, t + 1) = £ С+{+2ГCk—t—}—2r

i=r

асимптотически точна.

- - АХ УО - иррег

Рис, 1,1: Оценки из теорем 3 и 4 против оценки из теоремы 2 при к' = 0.5

- - АХ УО - Иррег

Рис, 1,2: Оценки из теорем 3 и 4 против оценки из теоремы 2 при к' = 0.1

Эту теорему мы докажем в параграфе 1.3.1.

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

Теорема 6. Пусть, как и в теореме 3,2к — £ ^ пи 0 ^ г ^ к — £. Положим £1 = 3£ + 2г — 2к и допустим, что 2(£ + 2г) — £1 ^ п. Тогда,

Идея доказательства этой теоремы довольно проста и перекликается с работой [40]. Мы помним (см. замечание после формулировки теоремы 3), что в конструкции Ллсведе Хичитряни из теоремы 3 фиксируется некоторое множество А мощности £ + 2г и рассматриваются все к-элементные множества, которые имеют с А больше £ + г общих элементов. Любые два таких к-элементных множества пересекаются больше, чем по £ элементам. А что, если мы теперь построим много таких конструкций, стараясь следить за тем, чтобы множества из разных конструкций пересекались меньше, чем по £ элементам? Оказывается, для этого достаточно просто взять много (£ + 2г)-элементных множеств, у которых попарные пересечения имеют мощности, не

£1

нам позволяет теорема 4.

Можно пойти дальше и попробовать применить теорему 4 дважды, взяв вместо £1 некоторое в > £ь Естественно, мы уже не можем гарантировать, что с пересечением любых двух множеств в такой конструкции все в порядке. Но мы можем выкинуть из конструкции что-то "вредоносное" и в итоге реализовать нужный запрет.

Теорема 7. Пусть 2к — £ ^ пи 0 ^ г ^ к — £. Положим £1 = 3£ + 2г — 2к и допустим, что 2(£ + 2г) — £1 ^ п. Пусть, далее, £1 < в < £ + 2г. Пусть, наконец, Т — такая совокупноешь (£ + 2г)-элементных множеств, что для любых двух множеств А, В Е Т вы,полнено |А П В| < в и

т(п, к, £) ^

Ес3

сг+2т сп—2т

3 =¿1

ЕгчЗ гч>

сг+2т с

3 с^+2т—3

'¿+2т сп—2т

Тогда

Ш(п, к, £) ^ И С^+^П—^г 1 — • Сп—2г 1 • ,т.аХ / ^ С/ ^^г—г+1

\ ¿1 <г<в ^—'

\ . =¿1

Можно устроить второе "прореживание", потребовав, чтобы разные £ + г-элементные множества пересекались максимум по £1 элементам внутри А П В и максимум по х элементам внутри А П В, где А и В — (£ + 2г)-элементные множества, задающие конструкции Алсведе-Хачатряна. Наконец, можно зафиксировать некоторое множество ^ = {1,... , /} С в котором мы будем проводить те же действия, как в предыдущих теоремах, а в выбор

"хвостиков" будет ничем не ограничен. В таком случае у нас появится еще один свободный параметр /: в наших обозначениях величина £ + г + I будет отвечать за мощность пересечения к-элементных множеств с

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

Теорема 8. Пусть, как обычно, 2к — £ < п. Пусть, далее, /, г,/,£1,й,х — натуральные числа, удовлетворяющие неравенствам

£ + г + I < к; £ + 2г + I < f < п; х < /;

2(£ + 2г) — f < £1 = 2£ + г — х — к < в < £ + 2г; п — f ^ к — £ — г — I — 1.

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

=

С ¿+2г

¿+2г

С+2г С/——2г

Тогда выполнена оценка

т(п,к,£) ^ И • C¿z/-г-1-1 • (С;+г+1С}—_2г — С1 — С2) С1 С2

С1 = ^ • С/ ——2г ,,таХУ^ С. С|++2Гг—.г+1,

1<г

/

С2 = • С+2+1таХ У^ +2г—гС/ —2,—4г+г.

. =х+1

Замечание 1. Задача отыскания величины, m(n, k, t) равносильна задаче о величине m(n, n — k,n — 2k+t). В самом деле, если |AПB| = t7 то дополнения множеств A, B7 имеющие мощности n — k, пересекаются по n — 2k + t элементам. Это, очевидно, позволяет еще усилить теорему 8 (и реально усиливает).

Поскольку в теореме 8 много разных параметров, вычисления оптимальных оценок за счет теоремы 8 и замечания 1 весьма затратны. Для ускорения процедуры построения графиков была предпринята попытка отыскания явной формулы для оптимального значения параметра f. При этом все параметры представлялись в нашем стандартном асимптотическом виде как функции вида ~ с' • n, n ^ то. Например, f ~ f'n. Итоговая оценка записывалась в форме (c(k', t', f', /', r', s', x') + o(1))n. Производная функции c(k',t', /', /',r', s',x') no f' приравнивалась к нулю, и с помощью ресурса Wolfram Mathematica была найдена формула (которая, кстати, свидетельствует о том, что в данном случае уравнение на производную преобразовывается к квадратному)

_ — B — VB2 — 4AC fopt = 2a ,

где

A = k' — r' + s' — t',

B = —(/' + 4k'r' — 2l'r' + s' (1 — k' + /' + r') + t'(2k' — /' — 2r' + s' — t')), C = (2r' + t')(/' + 2r' + t').

Разумеется, это лишь необходимое условие, и граница области оптимизации очень сложна, но численные эксперименты показали, что если подставлять в функцию c(k', t', /', /', r', s', x') fo'pt

f'

(надо лишь заменять fOpt единицей, еели fOpt > 1). К сожалению, для остальных параметров не удалось получить столь простых формул, и оптимальные значения x' и /', приводимые ниже, — результат численной максимизации. Так или иначе, наша цель — нижние границы, и на рисунках, которые мы приведем в следующем параграфе, показано, насколько границы из теоремы 8 вкупе с замечанием 1 сильнее всех своих частных случаев.

В то же время не может не возникнуть вопрос: а по делу ли такое количество параметров в теореме? Возможно, оптимум достигается при каких-то простейших ситуациях? Например, даже имея формулу для/Opt, можно допустить, что на самом деле почти всегда fOpt = 1. Также для /' есть тривиальный

случай, когда V = к'—£' —г', и касательно х': вполне можно рассмотреть лишь х' = /'. Конечно, сам факт превосходства теоремы 8 над частными случаями свидетельствует о том, что какие-то из параметров точно пригодились, но вот какие? На следующих трех рисунках мы покажем, что все параметры важны. На всех рисунках к' = 0.1. На первом из них видно, что далеко не всегда = 1 и что отличие оптимального параметра от единицы весьма значительно. На втором рисунке то же самое продемонстрировано относительно

/'. Наконец, последний рисунок говорит о том, что выбор нетривиального х'

Список литературы диссертационного исследования кандидат наук Бобу Андрей Викторович, 2019 год

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

[1] Erdos P., Ko Ch., Rado R. Intersection theorems for systems op finite sets // Quart. J. Math. Oxford Ser. (2). - 1961. - V. 12. - P. 313-320.

[2] Frankl P. The Erdos-Ko-Rado theorem is true for n = ckt // Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976). - 1978. - V. 1. - P. 365375.

[3] Wilson R. M. The exact bound in the Erdos-Ko-Rado theorem // Combinatorica. - 1984. - V. 4, N. 2-3. - P. 247-257.

[4] Ahlswede R., Khachatrian L. H. The complete nontrivial-intersection theorem for systems of finite sets //J. Combin. Theory A. — 1996. — V. 76. — P. 121-138.

[5] Ahlswede R., Khachatrian L. H. The complete intersection theorem for systems of finite sets. // Europ. J. Combin. — 1997. — V. 18. — P. 125136.

[6] Deza M.. Erdos P., Frankl P. Intersection properties of systems of finite sets // Proceedings of the London Mathematical Society. — 1978. — V. 3, N. 2. — P. 369-384.

[7] Hilton A. J. W., Milner E. C. Some intersection theorems for systems of finite sets // The Quarterly Journal of Mathematics. — 1967. V. 18. X. 1.

P. 369-384.

[8] Frankl P. On intersecting families of finite sets // Journal of Combinatorial Theory, Series A. - 1978. - V. 24, N. 2. - P. 146-161.

[9] Katona G. Intersection theorems for systems of finite sets // Acta Mathematica Hungarica. - 1964. - V. 15, N. 3-4. - P. 329-337.

[10] Kleitman D. J. On a combinatorial conjecture of Erdos // Journal of Combinatorial Theory. - 1966. - V. 1, N. 2. - P. 209-214.

[11] Milner E. C. A combinatorial theorem on systems of sets // Journal of the London Mathematical Society. - 1968. — V. 1, N. 1. — P. 204-206.

[12] Greene C., Katona G. 0. H., Kleitman D. J. Extensions of the Krdds Ko Rado Theorem // Studies in Applied Mathematics. — 1976. — V. 55, N. 1. — P. 1-8.

[13] Erdos P. A problem on independent r-tuples // Article in press B. Bollobas et al. / Journal of Combinatorial Theory, Series A. — 1965.

[14] Frankl P. On Sperner families satisfying an additional condition // Journal of Combinatorial Theory, Series A. - 1976. - V. 20, N. 1. - P. 1-11.

[15] Kleitman D. J. Maximal number of subsets of a finite set no k of which are pairwise disjoint // Journal of Combinatorial Theory. — 1968. — V. 5, N. 2. — P. 157-163.

k

disjoint members // Journal of Combinatorial Theory, Series A. — 2018. — V. 157. - P. 427-434.

[17] Kupavskii A. Diversity of uniform intersecting families // European Journal of Combinatorics. - 2018. - V. 74. - P. 39-47.

[18] Frankl P., Kupavskii A. Uniform s-cross-intersecting families // Combinatorics, Probability and Computing. — 2017. — V. 26, N. 4. — P. 517-524.

[19] Kupavskii A., Zakharov D. Regular bipartite graphs and intersecting families //Journal of Combinatorial Theory, Series A. — 2018. — V. 155. — P. 180189.

[20] Frankl P., Kupavskii A. Erdos-Ko-Rado theorem for {0, ±1}-vectors // Journal of Combinatorial Theory, Series A. — 2018. — V. 155. — P. 157179.

[21] Frankl P., Kupavskii A. Intersection theorems for {0, ±1}-vectors and s-cross-intersecting families // Moscow Journal of Combinatorics and Number Theory. - 2017. - V. 7, N. 2. - P. 91-109.

[22] Frankl P., Kupavskii A. A size-sensitive inequality for cross-intersecting families // European Journal of Combinatorics. — 2017. — V. 62. — P. 263271.

[23] Frankl P., Kupavskii A. Counting intersecting and pairs of cross-intersecting families // Combinatorics, Probability and Computing. — 2018. — V. 27, N. 1. - P. 60-68.

[24] Bollobas В., Narayanan B.P., Raigorodskii A.M. On the stability of the Erdos-Ko-Rado theorem // Journal of Combinatorial Theory, Series A. — 2016. - V. 137. - P. 64-78.

[25] Варим,мов P. P., Оценка числа сигналов в кодах с коррекцией ошибок // Доклады АН СССР. - Т. 117, № 5. - 1957. - С. 739-741.

[26] Gilbert Е. N., A comparison of signalling alphabets // Bell System Technical Journal. - V. 31, N. 3. - 1952. - P. 504-522.

[27] Hamming R. W., Error detecting and error correcting codes // Bell System technical journal. - V. 29, N. 2. - 1950. - P. 147-160.

[28] Вассалы,го Л. А., Новые верхние границы для кодов, исправляющих ошибки // Проблемы передачи информации. — Т. 1, № 4. — 1965. — С. 41-44.

[29] Левенштейн В. И.7 О верхних оценках для кодов с фиксированным весом векторов // Проблемы передачи информации. — Т. 7, № 4. — 1971. — С. 3-12.

[30] McEliece R.J., Rodemich E.R., Rumsey H.Jr., Welch L. R., New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities // IEEE Transactions on Information Theory. — V. 23, N. 2. — 1977. — P. 157166.

[31] Мак-Вильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки // М.: Радио и связь, 1979.

[32] Nagy Z. A certain constructive estimate of the Ramsey number // Matematikai Lapok. - V. 23, N. 301-302. - 1972. - P. 26.

[33] barman D. G., Rogers C. A. The realization of distances within sets in Euclidean space // Mathematika. - 1972. - V. 19. - P. 1-24.

[34] barman D. G. A note on the realization of distances within sets in Euclidean space // Commentarii Mathematici Helvetici. — 1978. — V. 53, N. 1. — V. 529-535.

[35] Erdós P. Problems and results in graph theory and combinatorial analysis // Proc. British Combinatorial Conj., 5th. — 1975. — C. 169-192.

[36] Frankl P. Extremal problems and coverings of the space // European Journal of Combinatorics. - 1980. - V. 1, N. 2. - C. 101-106.

[37] Frankl P., Wilson R. Intersection theorems with geometric consequences // Combinatorica. - 1981. - V. 1. - P. 357-368.

[38] Delsarte P., Goethals J.M., Seidel J.J. Spherical codes and designs // Geometriae Dedicata. - 1977. - V. 6, N. 3. - P. 363-388.

[39] Frankl P., Füredi Z. Forbidding just one intersection // Journal Combin. Theory A. - 1985. V. 39 P. 160-176.

[40] Rodl V. On a packing and covering problem // European Journal of Combinatorics. - 1985. - V. 6, N. 1. - P. 69-78.

[41] Balogh J., Kostochka A., Raigorodskii A. Coloring some finite sets in RN // Discussiones Mathematicae Graph Theory. — 2013. — V. 33, N. 1. — P. 25-31.

[42] Raigorodskii A. M. Combinatorial Geometry and Coding Theory // Fundamenta Informaticae. - 2016. - V. 145, N. 3. - P. 359-369.

[43] Пядеркин M. M.. Райгородский A. M. О случайных подграфах кнезеров-ского графа и его обобщений // Доклады Академии Наук. — 2016. — Т. 470, № 4. - С. 384-386.

[44] Pyaderkin М. М. On the stability of some Erdós-Ko-Rado type results // Discrete Mathematics. - 2017. - V. 340, N. 4. - P. 822-831.

[45] Черкашин Д. Д., Райгородский A.M. О хроматических числах пространств малой размерности // Доклады Академии Наук. — 2017. — Т. 472, № 1. - С. 11-12.

[46] Бобу А. В., Костина О. А., Куприянов А. Э. Числа независимости и хроматические числа некоторых дистанционных графов // Проблемы передачи информации. — 2015. — Т. 51, № 2. — С. 87-99.

[47] Frankl P., Rodl V. Forbidden intersections // Transactions of the Amer. Math. Soc. - 1987. - V. 300, N. 1. - P. 259-286.

[48] Frankl P., Rodl V. All triangles are Ramsey // Transactions of the Amer. Math. Soc. - 1986. - V. 297, N. 2. - P. 777-779.

[49] Frankl P., Rödl V. A partition property of simplices in Euclidean space // J. Amer. Math. Soc. - 1990. - V. 3, N. 1. - P. 1-7.

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

[51] Попомарепко Е. П., Райгородский А. М. Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения // Проблемы передачи информации. — 2013. — Т. 49, № 4. — С. 98-104.

[52] Пономаренко Е. И., Райгородский А. М. Улучшение теоремы Франк.m Уилсона о числе ребер гиперграфа с запретами на пересечения // Доклады Академии Наук. — 2014. — Т. 454, № 3. — С. 268-269.

[53] Пономаренко Е. П., Райгородский А. М. Новые верхние оценки чисел независимости графов с вершинами в {—1,0,1}n и их приложения в задачах о хроматических числах дистанционных графов // Математические заметки. - 2014. - Т. 96, № 1. - С. 138-147.

[54] Райгородский A.M., Сагдеев А. А. О хроматическом числе пространства с запрещенным правильным симплексом // Доклады Академии Наук. — 2017. - Т. 472, № 2. - С. 127-129.

[55] Сагдеев А. А. О нижних оценках хроматических чисел дистанционных графов с большим обхватом // Математические заметки. — 2017. — Т. 101, № 3. - С. 430-445.

[56] Просанов Р. П., Райгородский A.M., Сагдеев A.A. Улучшения теоремы Франкла-Редля и геометрические следствия // Доклады Академии Наук, _ 2017. - Т. 475, № 2. - С. 137-139.

[57] Sagdeev A.A. On a Frankl-Rödl theorem and its geometric corollaries // Electronic Notes in Discrete Mathematics. - 2017. - V. 61. - P. 1033-1037.

[58] Бобу А. В., Куприянов А. Э. О хроматических числах дистанционных графов, близких к кнезеровским // Проблемы передачи информации. — Т. 52, № 4. - 2016. - С. 64-83.

[59] Бобу А. В., Куприянов А. Э., Райгородский A. M. О хроматических числах дистанционных графов, близких к кнезеровским // Доклады Академии Наук. - Т. 468, № 3. - 2016. - С. 247-250.

[60] Balogh J., Cherkashin D., Kiselev S. Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs // arXiv preprint arXiv: 1805.09394. - 2018.

[61] Ray-Chaudhuri D.K., Wilson R.M. On ¿-designs // Osaka J. Math. — 1975. - V. 12, N. 3. - P. 737-744.

[62] Bahai L., Frankl P. On set intersections // Journal of Combinatorial Theory, Series A. - 1980. - V. 28, N. 1. - P. 103-105.

[63] Frankl P. Families of finite sets with prescribed cardinalities for pairwise intersections // Acta Mathematica Hungarica. — 1980 — V. 35, N. 3. — P. 351-360.

[64] Mubayi D., Rodl V. Specified intersections // Transactions of the American Mathematical Society. - V. 366, N. 1. - 2014. - P. 491-504.

[65] Бердников А. В., Райгородский A. M. О хроматическом числе евклидова пространства с двумя запрещенными расстояниями // Математические заметки. - Т. 96, № 5. - 2014. - С. 790-793.

[66] Бердников А. В. Оценка хроматического числа евклидова пространства с несколькими запрещенными расстояниями // Математические заметки. _ Т. 99. .у. 5. _ 2016. - С. 783-787.

[67] Hadwiger Н. Ein Uberdeckungssatz fur den Euklidischen Raum // Portugaliae Math. - 1944. - V. 4. - P. 140-144.

[68] Soifer A. The Mathematical Coloring Book // Springer, 2009.

[69] Brass P., Moser W., Pach J. Research problems in discrete geometry // Berlin: Springer, 2005.

[70] Moser L., Moser W. Solution to problem 10 // Canad. Math. Bull. - 1961. -у. 4. _ p. 187-189.

[71] de Grey A. D. N. J. The chromatic number of the plane is at least 5 // arXiv preprint arXiv:1804.02385. - 2018.

[72] Nechushtan O. On the space chromatic number // Discrete mathematics. — 2002. - V. 256., N. 1-2. - C. 499-507.

[73] Coulson D. A. 15-colouring of 3-space omitting distance one // Discrete mathematics. - 2002. - V. 256, N. 1-2. - C. 83-90.

[74] Szekely L. A. Erdos on unit distances and the Szemeredi-Trotter theorems // J. Bolyai Math. Soc. - 2002. - V. 11. - P. 649-666.

[75] Raigorodskii A. M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer. — 2013. — P. 429-460.

[76] Капель-Белов А. Я., Воронов В. А., Черкашин Д. Д. О хроматическом числе плоскости // Алгебра и анализ. — 2017. — Т. 29, № 5. — С. 68-89.

[77] Черкашин Д. Д., Райгородский А. М. О хроматических числах пространств малой размерности // Доклады Академии наук. — 2017. — Т. 472, № 1. - С. 11-12.

[78] Cherkashin D., Kulikov A., Raigorodskii A. On the chromatic numbers of small-dimensional Euclidean spaces // Discrete Applied Mathematics. — 2018. - V. 243. - P. 125-131.

[79] Raiskii D. E. Realization of all distances in a decomposition of the space Rn into n + 1 parts // Mathematical notes. - 1970. - V. 7, N. 3. - P. 194-196.

[80] Benda M.. Pedes M. Colorings of metric spaces 11 Geombinatorics. — 2000. - V. 9. - P. 113-126.

[81] Lovasz L. Self-dual polytopes and the chromatic number of distance graphs on the sphere // Acta Sci. Math. - 1983. - V. 45. - P. 317-323.

[82] Raigorodskii A. M. On the chromatic numbers of spheres in Rn 11 Combinbatorica. - 2012. - V. 32, N. 1. - P. 111-123.

[83] Купавский А. Б. О раскрасках сфер, вложенных в Rn // Матем. сборник, _ 2011. - Т. 202, № 6. - С. 83-110.

[84] Костина О. А., Райгородский А. М. О нижних оценках хроматического числа сферы // Доклады Академии Наук. — 2015. — Т. 463, № 6. — С. 639.

[85] Костина О. А., Райгородский А. М. О новых нижних оценках хроматического числа сферы // Труды Московского физико-технического института, _ 2015. - Т. 7, № 2. - С. 20-26.

[86] Berdnikov А. V. Chromatic number with several forbidden distances in the space with the /^-metric // Journal of Mathematical Sciences. — 2017. — V. 227, N. 4. - P. 395-401.

[87] Звонарев А. Е., Райгородский А. Л/.. Самиров Д. В., Харламова А. А. О хроматическом числе пространства с запрещенным равносторонним треугольником // Матем. сборник. — 2014. — Т. 205, № 9. — С. 97-120.

[88] Звонарев А. Е., Райгородский А. М. Улучшения теоремы Франкла-Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником // Труды Математического института им. В. А. Стеклова. - 2015. - Т. 288. - С. 109-119.

[89] Самиров Д. В., Райгородский A.M. Хроматические числа пространств с запрещенными одноцветными треугольниками // Матем. заметки. — 2013. - Т. 93, № 1. - С. 134-143.

[90] Самиров Д. В., Райгородский А. М. Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками // Итоги науки и техники, Современная математика и ее приложения. _ 2013. - Т. 125. - С. 252-268.

[91] Самиров Д. В., Райгородский А. М. Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками // Доклады Академии Наук. — 2014. — Т. 456, № 3. — С. 280-283.

[92] Самиров Д. В., Райгородский А. М. Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников // Труды МФТИ. —2015. —Т. 7, № 2. — С. 39-50.

[93] Фихтенголъц Г. М. Основы математического анализа // СПб: Лань, 2005.

[94] Graham R. L. Rothschild В. L., Spencer J. Н. Ramsey theory // New York: John Wiley k Sons, 1990.

[95] Райгородский A.M., Харламова A.A. О совокупностях (—1,0,1)-векторов с запретами на величины попарных скалярных произведений // Труды по векторному и тензорному анализу. — 2013. — Т. 29. — С. 130 146.

[96] Matovsek J. Using the Borsuk-Ulam theorem // Berlin: Springer, Universitext, 2003.

[97] Бобу A.B., Куприянов А. Э., Райгородский A.M. Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением // Матем. сборник. — 2016. — Т. 207, Л" 5. - С. 17-42.

[98] Бобу А. В., Куприянов А. Э., Райгородский А. М. О максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением // Доклады Академии Наук. — 2015. — Т. 463, № 1. — С. 11-13.

[99] Бобу А. В., Куприянов А. Э., Райгородский А. М. О числе ребер однородного гиперграфа с диапазоном разрешенных пересечений // Проблемы передачи информации. — 2017. — Т. 53, № 4. — С. 16-42.

[100] Бобу А. В., Куприянов А. Э., Райгородский А. М. О числе ребер однородного гиперграфа с диапазоном разрешенных пересечений // Доклады Академии Наук. - 2017. - Т. 475, № 4. - С. 365-368.

[101] Бобу А. В., Куприянов А. Э. Улучшение нижних оценок хроматического числа пространства с запрещенными одноцветными треугольниками // Труды МФТИ. - 2018. - Т. 10, № 4. - С. 14-23.