Верхние оценки в задаче Эрдеша-Хайнала и ее обобщениях тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Тепляков Сергей Михайлович

• Тепляков Сергей Михайлович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Тепляков Сергей Михайлович

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

4.2 Верхняя оценка для величины Шк(2к + д)

4.3 Свойства верхней оценки величины Шк(2к + д)

4.4 Верхняя оценка для величины Шк (г, г к + д)

4.5 Свойства верхней оценки величины Шк(г,гк + д)

4.6 Приложение

Заключение

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

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

Введение

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

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

Теория гиперграфов в целом и задача Эрдеши ХиМнили в частности возникли из смежной области математики — теории графов, которая, в свою очередь, является важным и крупным разделом дискретной математики. Напомним, что гиперграф — это пара (V, Е), где V — множество вершин, аЕ-произвольная совокупность подмножеств множества V. Таким образом, гиперграф отличается от обычного графа тем, что каждое ребро может содержать произвольное количество вершин. Основные определения, некоторые свойства и общий обзор задач, связанных с гиперграфами, можно найти в источниках: [1], [2], [3], [4]. В данной работе рассматривается важное подмножество класса всех гиперграфов — семейство п-однородных гиперграфов, то есть таких гиперграфов, у которых мощности всех ребер одинаковы и равны п. Прежде всего речь пойдет о способах раскраски вершин п-однородных гиперграфов, при которых ребра гиперграфа обладают теми или иными свойствами. Так, одно из рассматриваемых свойств — это обобщение классического свойства двудольности графа: мы требуем от гиперграфа, чтобы существовало такое разделение множества вершин на два подмножества, при котором в каждом его ребре есть по крайней мере один элемент из каждого подмножества. Довольно естественно предположить, что чем больше ребер в гиперграфе, тем вероятнее, что найти такие два подмножества не получится. Таким образом, возник вопрос об отыскании величины т(п), равной минимальному количеству ребер, необходимому для того, чтобы существовал гиперграф,

п

удалось посчитать точное значение величины т(п), а для всех прочих значений были найдены различные верхние и нижние оценки. Подробные обзоры задач, связанных с оценкой величины т(п), можно найти в работах [5], [6], [7]. Также отдельные результаты по верхним и нижним оценкам приведены в работах [8] - [12].

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

имеющего не более чем N ребер, где N - оценка снизу, которую мы пытаемся доказать, разделить все множество вершин на два подмножества случайным образом. Такое разделение подразумевает то или иное распределение всех способов раскраски и обычно называется случайной раскраской гиперграфа в два цвета. После чего задача сводится к тому, чтобы оценить вероятность того, что хотя бы одно ребро не является одноцветным. Действительно, если вероятность этого события строго меньше единицы, то существует такая раскраска, в которой одноцветного ребра нет. Именно таким способом получаются наилучшие на текущий момент нижние оценки в задаче о величине ш(п) и в ее обобщениях. Впервые вероятностный метод был применен в подобного рода задачах П. Эрдешем в 50-ые года XX века. Вероятностный метод использовался в множестве работ, связанных с отысканием оценок величины Ш( п)

Ш( п)

в работах в области случайных графов (см. [22] - [25]), а также, например, в

к

Ш( п)

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

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

ства вершин в два цвета, при которой любое ребро гипеграфа содержит менее к

кп

об улучшении верхней оценки величины Шк (п). Нам удалось расширить об-

к

В четвертой главе мы сформулируем и докажем верхние оценки, а также рассмотрим и другие свойства величины Шк(п) для значений параметра к, близких кп/2. Эта задача близка с известной задачей об уклонении ([15], с.287-295).

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

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

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

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

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

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

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

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

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

1. Получены новые рекуррентные верхние оценки величины тк (п), равной

п

свойством Вк (т.е. не допускающего раскраски в два цвета, при которой в любом ребре гиперграфа вершин каждого цвета по крайней мере к). А именно, для любых натуральных к, I и а > 2к, Ь > 21 выполнено:

та1+Ък-к1+к+1-а-ъ(аЬ) < тк(а)(иц(Ь))а. (Теорема 1)

Далее, справедливо, что

тк(п) < тк(п — 2) • (п — к + 1) + 2п-к+1. (Следствие 1)

Наконец,

тк (п) < тк (п — 1) • (п — к + 1) + 1. (Следствие 2)

2. Получена верхняя оценка величины mk(n) для всex k = o(n). А именно, при условии k = o(n) справедлива оценка

. , e ln 2 о 2 . . ,, mk(n) < — n'-k-^(1+ o(l))

4 0 Cn

при n —у oo (теорема 3).

3. Получены новые верхние оценки для величины uj(f,q,M), равной отношению количества тех значений параметра к, меньших M, к M, при которых mk(2k + q) не превосходит функцию натурального аргумента f(k)

4. Получены новые верхние оценки для величины mk(n,r), равной мини-

n

свойством Bk (r) (т.е. не допускающего рас краски в r цветов, при которой в любом ребре гиперграфа вершин каждого цвета по крайней мере к). А именно, для целого числа q > 0 и натурального r > 2 справедливо

mk(r, rk + q) < C • (ln k)q+1.

(теорема 6). Также получены оценки для величины w(f,q, M, r), равной отношению количества тех значений параметра k, меньших M, к M, при которых mk (r, rk + q) не превосходит функцию натурального аргумента f(k)

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

Материалы диссертации опубликованы в 3 работах ([27], [28], [29]). Работы [27] и [29] опубликованы в издании, состоящем в RSCI, а работа [28] в издании, входящем в Web of Science. Также результаты работы докладывались на научных семинарах под руководством профессора A.M. Райгородского в МГУ им. М.В. Ломоносова (кафедра математической статистики и случайных процессов, механико-математический факультет), научном семинаре кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносва. Достоверность полученных результатов также подтверждается применением современных методов экстремальной комбинаторики и теории гиперграфов.

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

Гл яв ^^

Краткая история задачи и основные определения

В данной главе мы расскажем об истории задачи Эрдеши Хи Мнили и кратко сформулируем те вопросы, которые мы изучим в следующих главах. Прежде всего напомним, что гиперграф — это пара Н = (V, Е), где V — конечное

Е

ная совокупность различных подмножеств множества V, называемых ребра-

п

п

п

гиперграфа не слишком много ребер (например, не больше, чем2п—^ то вершины этого гиперграфа допускают раскраску в два цвета, при которой все ребра гиперграфа неодноцветны (содержат вершины обоих цветов). Это привело к рассмотрению величины т(п), равной наименьшему т € М, такому,

пт нельзя раскрасить в два цвета с соблюдением условия неодноцветности всех ребер.

Следуя, опять же, Эрдешу и Хайналу, можно сформулировать определе-

В

его вершин в два цвета, при которой все его ребра неодноцветны; тогда

т(п) = шт{|Е| : Н = (V, Е) — п-однородный гиперграф, Н те обладает свойством В}.

Сейчас известно, что

0.1 (1/2 2П < т(п) < е(1п2)п22п—2(1 + о(1)). (1.1)

V 1^1 п /

Нижняя оценка принадлежит Дж. Радхакришнану и А. Сринивасану (см. [21]), а верхняя — Эрдешу (см. [31]). Отметим, что проблематика, возникшая

за полвека с момента постановки задачи, крайне обширна и разнообразна. Обзор многочисленных результатов в этой области можно найти, например, в статье [5].

Одно из наиболее естественных обобщений величины m(n) было предложено A.M. Райгородским и Д.А. Шабановым в 2003 году (см. [32]). А именно, скажем, что гиперграф обладает свойством если его вершины можно так раскрасить в два цвета, чтобы каждое его ребро содержало не меньше k вершин первого цвета и не меньше k вершин второго цвета. Разумеется, если гиперграф n-однороден, то k < Соответственно,

mk(n) = min{|E| : H = (V, E) — n-однородный гиперграф, H те обладает свойством Bk}.

Попятно, что mi(n) = m(n).

Поскольку величина mk (n) зависит от двух параметров, устроена она слож-

m( n)

разных оценок для mk (n), и их подробный обзор можно найти в статье [6]. Приведем здесь различные верхние и нижние оценки величины mk (n), известные на текущий момент. Нижние оценки:

1) Если к = k(n) таково, что k < y ln n, где

0 < y < (2 + 4ln2)-1, то при n ^ ж наибольшая оценка, полученная в работе [33

/ n \ 2 21-ke-2 2n-1

mk(n) > c -- . -z^i—r.

k( ) - Vlnn) Ckn-1

2) Если же k — (2 + 4ln2)-1 lnn и 2k2(n — k) < (n — 2k)2, то при n ^ ж

наибольшей является оценка, полученная в работе [34]:

2n-1

mk (n) — 0. 19n1/4

Ch-1'

3) Наконец, если 2к2(п - к) > (п - 2к)2, то наибольшей является оценка, полученная вероятностным методом в работе [6]:

/ ч 2П-1

Шк (п) >

\^k-1 Ci 0 Cn

Верхние оценки:

1) Если к удовлетворяет соотношению к = о(^) ПРИ п ^ то, то асимптотически наименьшей является оценка, полученная в работе [32],

р 1п 2 2п

тк(п) < —^-¿-т-(1+ 5(1)). (1.2)

4 1^1=0 Сп

2) Также применима следующая универсальная асимптотическая оценка. В частности, она справедлива и в случае С1п < к < С2п, где 0 < С1 < С2 <

р 1п 2

тк(п) < т(п — к + 1) < • (п — к + 1)2 • 2п—к+1(1 + 5(1)). (1.3)

Из вида оценок (1.2) и (1.3) становится ясно, что эти результаты являются асимптотическими и из них невозможно понять, какие значения принимает

кп

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

кп

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

Продолжая говорить об оценках (1.2) и (1.3), можно также сделать вывод, что малоизученной остается и область значений к, близких к п/2 при п ^ то. Нижняя оценка становится тривиальной, а верхняя оценка асимптотически

к

ка, доказанная в работе [35]. Утверждается, что для любого целого д > 0 существует константа С > 0, что справедлива оценка

тк(2к + д) < С(1п к)9+1. (1.4)

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

к1,..., ks,...,

где к < ку для г < ^ при которых величину тк8 (2к5 + д) можно оценить функцией, возрастающей медленнее, чем 1п9+1(к) при й ^ то. Более того, существуют такие последовательности

к1,..., ...,

при которых эта функция оценивается сверху константой. Мы попытались

к

ной функции / натурального аргумента к выполнена оценка тк(2к + д) <

f (k). Для этого ввели специальное обозначение

u(f,q,M)

{k : k < M,mk(2k + q) < f (k)}

M

В главе 4 мы докажем нижнюю оценку для величины ш(/,д,Ы) при подстановке вместо функции / произвольной константы С > 0н, кроме того,

Также в главе 4 рассматривается и еще одно обобщение классической величины ш(п). Скажем, что гиперграф Н = (V, Е) обладает свойством Вк(г), если существует раскраска его вершин в г цветов, такая, что в любом ребре е € Е число вершин каждого из цветов, по крайней мере, к. Тогда определим Шк(г, п) как минимальное число ребер п-однородного гиперграфа, не обладающего свойством Вк(г). № определения следует, что в случае г = 2 мы получаем задачу о величине Шк (п). Для этого обобщения также возникает задача поиска верхней оценки для значений к, близких кп/г. Нам удалось доказать, что для произвольного целого д > 0 существует такая константа С>0

Аналогично случаю г = 2 для заданной функции / натурального аргумента и произвольного г € N такого, что г > 2 , введем обозначение:

Оказалось, что для величины u(f, q, M, r) также можно доказать оценку снизу. Кроме того, справедливо, что

lim u(f, q, M, r) = 1.

M

Эти утверждения мы докажем в главе 4.

м

lim u(f,q,M) = 1.

mk(r, rk + q) < C • (ln k)q+1.

и(f,q, M, r)

{k : k < M, mk(r, rk + q) < f (k)}

M

ГлВВ8) 2

Рекуррентные верхние оценки в задаче Эрдеша-Хайнала и в ее обобщениях

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

т( п) п

быть решена при помощи асимптотических оценок (1.1). В результате этой задаче был посвящен целый ряд работ, в которых были получены явные ре-

т( п)

Во-первых, X. Аббот и Л. Мозер показали (см. [36]), что

т(аЬ) < т(а)(т(Ь))а. (2.1)

Поскольку равенства т(2) = 3, т(3) = 7 очень просты, утверждение Аббота-Мозера позволяет делать явные оценки и для других значений параметров. При этом асимптотически оно гораздо слабее (1.1).

Во-вторых, X. Аббот и Д. Хансен установили (см. [37]) неравенства

т(п) < т(п — 2)п + 2п—1, п = 2к + 1, (2.2)

т(п) < т(п — 2)п + 2п—1 + 2п—2, п = 2к, (2.3)

т(п) < (2п — 1)(т(п — 2) + 1). (2.4)

п

т(п) < т(п — 2)п + 2п—1 + 1 С£/2. (2.5)

Все перечисленные оценки по-своему важны. Например, из результатов

т(4) < 27

шают до т(4) < 24, а Тофт — до т(4) < 23; последний факт есть текущий рекорд, который, по-видимому, усилить нельзя (хотя известно лишь, что т(4) > 17). В то же время го неравенства (2.1) получается, чтот(6) < 147, тогда как, из неравенств (2.3) и (2.4),

т(6) < 6т(4) + 32 + 16 < 186, т(6) < 11(т(4) + 1) < 264,

а из неравенства (2.5), т(6) < 180.

Для свойства Вк известна оценка, полученная Д. Шабановым

тк(п) < тк—1(п — 1) < ... < т(п — к + 1)

(см. [6]), так что теперь мы можем применять к ней рекурсии Аббота Мозера. Аббота Хансена или Тофта. Этими утверждениями исчерпывается множе-

кп

т2(4) = 4 ,т2(5) = 7 ,тз(7) < 8 ,т4(9) < 8

(см. [39]).

Нам удалось получить рекуррентные соотношения непосредственно для величин тк (п). Для этого мы использовали подход склейки нескольких гиперграфов, похожий на те, что использовались в неравенствах Аббота-Мозера, Аббота-Хансена и Тофта. Однако мы использовали совершенно новые конструкции гиперграфов, необходимые для такого подхода. Соответственно, в разделе 2.2 мы приведем и докажем оценки, которые служат в некотором смысле обобщениями неравенства (2.1); в разделе 2.3 мы сформулируем и докажем новые результаты типа (2.2) - (2.5). В разделе 2.4 мы обсудим оценку (1.1) и поймем, что она тоже может быть сделана явной (т.е. устраним величину о(1) из нее). Наконец, в разделе 2.5 мы проведем детальный анализ соотношений между оценками из разделов 2.2-2.4 и выпишем в итоге наилучшие из полученных нами неравенств для тк (п) при некоторых малых п к

Все результаты данной главы опубликованы в работе [27].

2.2 Обобщение подхода Аббота-Мозера

В своей работе [36] Аббот и Мозер применили принцип, основанный на

В

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

Вк

гци гиперграфа, не обладающего свойством В/. В итоге возникает

Теорема 1. Для любых натуральных к, I и а > 2к; Ь > 2/ вы,полнено:

та/+Ьк—к/+к+/—а— ь(аЬ) < тк(а)(т/(Ь))а. (2.6)

Доказательство.

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

Возьмем а-однородный гиперграф Н = (V,, Е), который имеет Шк(а) ребер

Вк

V = {1, 2,... ,у}.

Пусть Н1 = (VI, Е1) — ^-однородный гиперграф с Ш1 (Ь) ребрами, который не обладает свойством В/. Рассмотрим Н = (V,Е^), Ь = 2,...,г>, — непе-

Н1 аЬ

гпперграф Н = (V, Е) следующим образом. Положим

V

^ = и V.

¡=1

Пусть Н € Е — некоторое ребро гиперграфа Н следующего вида:

Н = {в1,... ,ва}.

Тогда рассмотрим совокупность

Ен = {¡1 и ... и ¡а : ¡г € Ен ,г = 1,... ,а}

всевозможных объединений ребер гиперграфов Н31,..., Н3а7 взятых по одному из каждого гиперграфа. Получается (ш/(Ь))а подмножеств множества V,

аЬ

Е = и Ен.

НеЕ

Из построения следует, что Н = (V, Е) — аЬ-однородный гиперграф, у которого Шк(а)(щ/(Ь))а ребер. Проверим, что он не обладает свойством

Ва/+Ьк-к/+к+/-а-Ь.

Пусть р — произвольная раскраска множества V в 2 цвета. Тогда р задает двухцветные раскраски на всех множествах V, £ = 1,..., V. В силу того, что все Нг не обладают свойством В/7 в каждом из гиперграфов найдется ребро, содержащее менее I вершин одного цвета. Такое ребро мы обозначим ег (если

таких ребер несколько, то возьмем любое из них). Рассмотрим следующую раскраску множества V вершин гиперграфа И: вершине

г е V = {1,..., V}

сопоставляем цвет, который "доминирует" в ребре ег (т.е. тот цвет, в который окрашены более чем Ь — / вершин). Получается некоторая раскраска р множества V в два цвета. В силу того, что И не обладает свойством Вк, найдется ребро ^о, которое в раекраске р имеет по крайней мере а — к + 1 вершин одного цвета (скажем, "красного"). Из построения множества Енс следует, что

е = и ег е Е^с.

геНс

Как мы знаем, среди ребер ег, входящих в состав ребра е, есть те менее а—к+1 ребер, в каждом из которых не менее Ь — / + 1 вершин красного цвета. Таким образом, мы нашли ребро гиперграфа И, имеющее по крайней мере

(а — к + 1)(Ь — / + 1)

аЬ

ладает свойством Ва/+Ьк—к/+к+/—а—Ь. Теорема доказана.

Рассматривая частный случай при / = к = 1 мы возвращаемся к неравенству (2.1) Аббота-Мозера.

2.3 Обобщение подхода Тофта

В работе [38] Тофта используется идея "склейки" так называемых критических гиперграфов. Для того чтобы обобщить эту идею, введем специальное понятие Вк-критического гиперграфа, то есть такого гиперграфа И = (V, Е),

Вк

ся из него выбрасыванием ребра, обладает этим свойством. В нижеследующем утверждении 1 мы приведем пример гиперграфа, не обладающего свойством Вк Вк

Утверждение 1. Пусть п,/ — натуральные числа, причем п > 2, а / < |. Рассмотрим множество вершин

V/1 = {х1,... ,Ж2/—1,аь ... ,ап,Ь1,..., Ьп} 1

и множество ребер Е}, состоящее из таких ребер Л, что

А = {х1,... ,Ж2/—1,аг,Ьг},

где £ € {1,... ,п - I + 1}, или,

А = {Cl, . . . , ^-/^^п-^,, . . . , an},

где сг = аг или сг = Ьг. Подчеркнем,, что гиперграф Н/1 = ^1,Е/1) имеет 2п + 21 - 1 вершин, п - I + 1 ребер размера 21 + 1 и 2п-1+1 ребер размера п. Тогда гиперграф = (V/1, Е1) не обладает свойством В/.

Утверждение 1 — аналог утверждения, сформулированного Тофтом в [38 и в нем построен гиперграф, не обладающий свойством В/ с некоторым I

с < §)•

Доказательство.

От противного. Пусть Н/1 все же обладает свойством В/. Тогда заметим, что в правильной раскраске существуют две возможности: либо ровно I - 1 вершина среди

Х1,.. . ,Х2/-1

раскрашена в один из цветов и I вершин — в другой, либо I - 2 вершины раскрашены в один цвет и I+1 вершин — в другой. Очевидно, в обоих случаях среди ребер

{С1,..

где сг = аг или сг = Ьг, найдется ребро, содержащее по крайней мере п - I + 1 вершин одного цвета, а значит, вершин другого цвета — не более I - 1. Противоречие.

Утверждение 2. Пусть п,1 — натуральные числа, причем I < Рассмотрим гиперграф Н/ = (У^,Е2)7 у которого

V/2 = {У1,У2, . . .,уп,х1,х2, . . .,Х2/-1} и А € Е27 если и только если

А = {Х1,Х2, . . . ,Х2/-1,Уг}, где £ = 1, 2,... ,п - I + 17 или,

А = {У1,У2,...,Уп}. Этот гиперграф является В/-критическим.

Доказательство.

От противного. Пусть И/2 все же обладает свойством В/. Тогда заметим, что в каждом ребре

Л = {Ж1,Ж2, . . . ,Х2/—1,Уг},

г = 1, 2,..., п — / + 1, все у раскрашены в один и тот же цвет, но тогда в ребре

Л = {У1,У2,...,Уп}

очевидно, найдется п — / + 1 вершин одного цвета, а значит, вершин другого цвета не больше / — 1. Противоречие.

Из построения гиперграфа И/ видно, что он является критическим. Таким образом, утверждение доказано.

Теперь, используя определения гиперграфов И/1 и И/2, введенные в утверждениях выше, сформулируем теорему, которая позволит нам получить оценки для величины тк (п). Справедлива

Теорема 2. Зафиксируем натуральные числа п, к, / с условиями п > 2, к > I и I < 2. Пусть И1 и И2 — два непересекающихся гиперграфа,

И1 Вк И2

— это либо гиперграф И/1, либо И2 с соответствующими параметрамип, /.

И

V(И) = V(И1) и (V(И2) \ {Х1,..., Х2/—1})),

Е (И) = (Е (И2 \{Х1 ,...,Х2/—1}))и и{Л | Л = Лг и В,- , Лг е Е (И1) , В, и{х1,...,х2/—1}е Е (И2)}. И Вк

И1

Вк И2 В И 1

И 2 И2 = И 1 И2 = И 2

совпадают. Ниже мы приведем общее рассуждение, верное в обоих случаях.

И

Вк

р множества вершин V = V(И) в 2 цвета. Поскольку И1 не обладает свойством Вк, то при раскраске р множества V(И1) с V(И) существует ребро Лг е Е (И1) в ^^^^^^м не более чем к — 1 вершина раскрашена (без ограничения общности) в первый цвет. Далее, вершины из множества

V(И2) \{Х1,...,Х2/ — 1}

р Н2

В/

меньше I. Это ребро может содержать все вершины

Х1,.. . ,Х2/-1,

Н/1 Н/2

просто нет). Рассмотрим оба случая.

Н2

Х1,.. . ,Х2/-1,

раскрашены правильно (то есть каждое ребро имеет по крайней мере I вершин каждого цвета). Тогда найдется такой набор вершин Bj7 что

В3 и{Х1,...,Х2/-1} € Е(Н2)

и ни одна из вершин Bj не раскрашена в цвет 1. В самом деле, если это не так, то вершины

Х1, . . . , Х/-1 можно раскрасить в цвет 1, а вершины

Х/,... ,Х2/-1

Н2 В/ ребро Аг и В_7 гиперграфа Н. Оно содержит не более к - 1 вершин цвета 1, что противоречит изначальному предположению о наличии свойстваВк у Н. Случай 2. Существует ребро

е € Е(Н2 \ {Х1,.. .,Х2/-1}),

в котором вершин одного из цветов меньше I. Тогда, поскольку е € Н, гиперграф Н те обладает свойством В/, а следовательно, и свойством ведь к > I. Опять получаем противоречие. Теорема доказана.

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

Следствие 1. Имеет место оценка:

Ши(п) < (п - к + 1)Шк(п - 2) + Т-к+1. (2.7)

Доказательство следствия 1. Воспользуемся теоремой 2. В качестве гиперграфа ^возьмем лю бой (п - 2)-однородный гиперг раф с Шк (п - 2)

Вк Н1 Вк

В качестве гиперграфа Н2 возьмем гиперграф НЦ.

Н

п Вк

время

1Е(Н)| = 1Е(Н1 )| • (п - I + 1) + 2п-/+1.

Значит,

Шк(п) < (п - I + 1)Шк(п - 2) + 2п-/+1 .

Замечая, что по условию теоремы 2 выполнено неравенство I < к, и подставляя I = к, получаем искомую оценку. Следствие доказано.

Следствие 2. Имеет место оценка

Шк(п) < (п - к + 1)Шк(п - 1) + 1. (2.8)

Доказательство следствия 2. Воспользуемся теоремой 2. В качестве гиперграфа ^возьмем лю бой (п - 1)-однородный гиперг раф с Шк (п - 1) ребрами, не обладающий свойством В^. Тогда Н^, очевидно, Вк-крнтическнй. В качестве гиперграфа Н2 возьмем гипер граф Щ.

Заметим, что гиперграф получаемый с помощью конструкции из тео-п Вк

время

1Е(Н)| = 1Е(Н1)| • (п - I + 1) + 1.

Значит,

Шк (п) < (п - I + 1)Шк (п - 1) + 1. Подставляя I = к, получаем искомое неравенство. Следствие доказано.

2.4 Верхние оценки величины Шк(п) с помощью систем общих представителей

Оценка (1.2) была получена с помощью так называемых систем общих представителей (с.о.п.). Напомним основные определения. Пусть

^п = {1,...,п}-

множество, состоящее из n элементов. Пусть, далее,

M = {Mi,...,Ms}-

совокупность любых подмножеств Положим k = min |Mi|. Рассмотрим

i=1,...,s

произвольное множество S С обладающее тем свойством, что SП Mj = 0 для каждого j Е {1,..., s}. Такое множество S называется системой общих

M

Z(n, s, k) = maxmin{|S| : S является с.о.п. для M}. m

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

Утверждение 3 (Д. А. Шабанов [33]). Пусть v Е N n Е N k Е Nc

условиями n < |7 k < |. Тогда при,

k_i

a = СП , b = mm £ • j + Cj • C?_') , c = 2v

x j=0

имеем,

mk(n) < min Z(a,c, b).

v

Неравенство (1.2) получается из утверждения 3 и следующего утверждения, в котором дается явная оценка величины Z(n, s, k).

n, s, k

место неравенство

n n sk n { TiTln— У

Z (n,s,k) < maxj Pkln -nj+k+L

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

М = {МЬ...,М8}.

Возьмем такой элемент V. е что количество множеств из М, которые его содержат, максимально. Это будет первый элемент с.о.п. Нетрудно видеть,

что он служит представителем для не менее множеств из М. Значит, непредставленными остались

вк

з1 < в -

п

множеств, причем все они находятся в

\Ы = &п-1.

Продолжая процедуру, берем элемент у2 € &п-1, который принадлежит не менее [П-11 множествам М. И так далее, покуда не исчерпаем всю совокупность М.

В дальнейшем, строя наилучшим образом оценки для Шк(п) с помощью систем общих представителей, мы перебираем все возможные значения величины V из утверждения 3, для каждого из таких значений берем параметры а, Ь, с и оцениваем ((а, с, Ь) с помощью описанного "жадного" алгоритма. Эти расчеты осуществлены на компьютере. Мы приведем их в следующем разделе 2.5. Также мы проведем сравнение этих результатов с результатами, получаемыми при помощи оценок (2.6)-(2.8).

2.5 Сопоставление результатов

В нашей работе мы получили рекуррентные соотношения (2.6), (2.7), (2.8). Кроме того, мы знаем оценку Шабанова

Шк(п) < Шк-1(п - 1) < ... < ш(п - к + 1) (2.9)

и метод получения оценок с помощью с.о.п. Попытаемся сравнить все эти результаты между собой. Рассмотрим к = 2, Зи п < 10. Напомним, что

ш(2) = З , ш(з) = 7 , ш(4) < 23 ,ш(6) < 147.

Заметим, что, исходя из неравенств (2.1) - (2.5), выписанных в разделе 2.1,

ш(5) < 51 , ш(7) < 421 , ш(8) < 1339 ,ш(9) < 2401 ,ш(10) < 7803.

Также в работе [39] получены соотношения

Ш2(4) = 4 , Ш2(5) = 7 ,шз(7) < 8 ,Ш4(9) < 8.

Наконец, равенство шз (6) = 3 очевидно.

Посмотрим на неравенство (2.6). В нем есть параметры к, I € N. Первый из них можно перепутать с индексом величины Шк (п). Поэтому переобозначим

его через к Ясно, что величины к, / не равны одновременно единице, т.к. в этом случае мы возвращаемся к величине ш(п). Пусть сперва к = 1, / = 2. Мы знаем, что а > 2к, Ь > 2/, т.е. а > 2 Ь > 4. Сама оценка имеет вид

та+1(аЬ) < ш(а)(ш2(Ь))а.

Нас интересуют только числа к = 2,3 и п = аЬ < 10, поэтому л ибо а = 2, Ь = 4 либо а = 2 Ь = 5, и видно, что при к = 2 оценка не работает. Если теперь к = 2 / = 1 т0 опять к > 3 и в нужных нам ситуациях либо а = 4, Ь = 2, либо а = 5 Ь = 2 В итоге получаем тз(8) < 48 и тз(10) < 147.

Список литературы диссертационного исследования кандидат наук Тепляков Сергей Михайлович, 2018 год

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

[1] А. А. Зыков, "Гиперграфы", УМЕ, 29:6 (1974), 89-154.

[2] С. Berge, Graphes et hypergraphes, Dunod, Paris, 1970.

[3] B. Bollobas, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge Univ. Press, 1986.

[4] J. L. Gross, J. Yellen, Handbook of Graph Theory, CRC Press, 2004.

[5] A. V. Kostochka, "Color-Critical Graphs and Hypergraphs with Few Edges: A Survey", More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15, eds. E. Gyori, G. О. H. Katona, L. Lovasz, Springer, 2006, 175198.

[6] A. M. Райгородский, Д. А. Шабанов, "Задача Эрдеша - Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы", Успехи Математических Наук, 66:5 (2011), 109-182 .

[7] P. Erdos, "Some old and new problems in various branches of combinatorics", Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium XXIII, Winnipeg: Utilitas Mathematica, 1979, 19-37.

[8] L. Lovasz, "A generalization of Konig's theorem", Acta Mathematica of the Academy of Sciences, Hungary, 21 (1970), 443-446.

[9] L. Lovasz, "Coverings and colorings of hypergraphs", Congressus Numer., 8 (1973), 3-12.

[10] P. D. Seymour, "On the two-coloring of hypergraphs", Quart. J. Math. Oxford, 25 (1974), 303-312.

[11] D. R. Woodall, "Property В and four-color problem", Combinatorics, Institute of Mathematics and its Applications, Southend-on-sea, England, 1972, 322340.

[12] М. И. Бурштейн, "Критические гиперграфы с минимальным числом ребер", Доклады АН Грузинской ССР; 83 (1976), 285-288.

[13] P. Erdos, "On a combinatorial problem, I", Nordisk Mat. Tidskrift, 11 (1963), 5-10.

[14] P. Erdos, "On a combinatorial problem, II", Acta Mathematica of the Academy of Sciences, Hungary, 15:3-4 (1964), 445-447.

[15] H. Алон, Дж. Спенсер, Вероятностный метод, М.: Бином. Лаборатория знаний, 2007.

[16] W. М. Schmidt, "Ein kombinatorisches Problem von P. Erdos and A. Hajnal", Acta Mathematica of the Academy of Sciences, Hungary.; 15 (1964), 373-374.

[17] P. Erdos, L. Lovasz, "Problems and results on 3-chromatic hypergraphs and some related questions", Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, 10, Amsterdam: North Holland, 1973, 609-627.

[18] J. Beck, "On a combinatorial problem of P. Erdos and L. Lovasz", Discrete Mathematics, 17:2 (1977), 127-131.

[19] J. Beck, "On 3-chromatic hypergraphs", Discrete Mathematics, 24:2 (1978), 127-137.

[20] J. H. Spencer, "Coloring n-sets red and blue", J. Combinatorial Theory, Series A, 30:1 (1981), 112-113.

[21] J. Radhakrishnan, A. Srinivasan, "Improved bounds and algorithms for hypergraph two-coloring", Random Structures and Algorithms, 16:1 (2000), 4-32.

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

[23] В. Bollobas, Random Graphs, Cambridge University Press, Cambridge, 2001.

[24] T. Luczak, S. Janson and A. Rucinski, Random Graphs, A Wiley-Interscience, New York, 2000.

[25] В.Ф. Кол чин. Случайные графы, М.: Физматлит, 2000.

[26] А. А. Вороненко, Н. К. Воронова, В.П. Ильютко "О существовании универсальных функций для класса линейных k-значных функций при небольших к", Прикладная математика и информатика51 (2013), 100108.

[27] С.М. Тепляков, "Верхняя оценка в задаче Эрдеши Хиинили о раскраске гиперграфа", Математические заметки, 93:1 (2013), 148-151.

[28] С.М. Тепляков, "Рекуррентные верхние оценки в задаче Эрдеши Хиинили о раскраске гиперграфа и в ее обобщениях", Труды МФТИ, 4:1(13) (2012), 141-150.

[29] С.М. Тепляков, "О многоцветных раскрасках гиперграфов", Труды, МФТИ, 9:1(33) (2017), 22-38.

[30] P. Erdos, A. Hajnal, "On a property of families of sets", Acta Mathematica of the Academy of Sciences, Hungary, 12:1-2 (1961), 87-123.

[31] P. Erdos, "On a combinatorial problem, II", Acta Mathematica of the Academy of Sciences, Hungary, 15:3-4 (1964), 445-447.

[32] Д. А. Шабанов, "Об одной комбинаторной задаче ЭрдешаДоклады Академии Наук, 396:2 (2004), 166-169.

[33] Д. А. Шабанов, "Рандомизированные алгоритмы раскрасок гиперграфов", Математический сборник, 199:7 (2008), 139-160.

[34] А. П. Розовская, "О двухцветных раскрасках общего вида для равномерных гиперграфов", Доклады Академии Наук, 429:3 (2009), 309-311.

[35] Черкашин Д., Куликов А., "О двухцветных раскрасках гиперграфов", Доклады РАН, 436:3 (2011), 316-319.

[36] A. L. Abbot, L. Moser, "On a combinatorial problem of Erdos and Hajnal", Canadian Mathematical Bullettin, 7 (1964).

[37] H. L. Abbot, D. Hanson, "On a combinatorial problem of Erdos", Canadian Mathematical Bullettin, 12 (1969), 823-829.

[38] B. Toft, "On color critical hypergraphs", Infinite and Finite Sets, eds. A. Hajnal et. al., Amsterdam: North Holland, 1975, 1445-1457.

[39] А. П. Розовская, M. В. Титова, Д. А. Шабанов, "О половинных раскрасках гиперграфов", Фундаментальная и прикладная математика, 15:7 (2009), 141-163.

[40] А. М. Райгородский, "Системы общих представителей в комбинаторике и их приложениях", Москва, МЦНМО, 2009.

[41] А.А. Карацуба, Основы аналитической теории чисел, М.: "Эдиториал УРСС", 2004.

[42] B. Rosser, "The n-th Prime is greater than n log n", Proc. London. Math. Soc., (1938), 45, 21-44.