Задача Эрдеша-Хайнала о раскрасках гиперграфов и смежные вопросы тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Акользин Илья Александрович

• Акользин Илья Александрович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Акользин Илья Александрович

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

1.4.2 Верхняя оценка, доказательство теоремы

1.5 Доказательства оценок в локальном варианте проблемы Эрдгша Хайпала

1.5.1 Нижняя оценка ((п, г), доказательство теоремы

1.5.2 Верхняя оценка ((п, г), доказательство теоремы

2 Исследование задачи Эрдеша Хайпала для малых значений параметров

2.1 История задачи Эрдеша-Хайнала для малых значений параметров

2.2 Формулировка нового результата

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

2.3.1 Простые оценки числа ребер в гиперграфах с большим хроматическим числом

2.3.2 Первые оценки

2.3.3 Случай V =

2.3.4 Случай V =

2.3.5 Случай V =

2.3.6 Случай V =

3 Задача о справедливых раскрасках гиперграфов

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

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

3.2.1 Алгоритм перекраски

3.2.2 Построение ^-дерева

3.2.3 Случай 1: ребро с большим числом потомков

3.2.4 Случай 2: гипердерево

3.2.5 Случай 3: большое поддерево

3.2.6 Случай 4: короткие циклы длины >2

3.2.7 Случай 5: короткий цикл длины

3.3 Локальная лемма

3.4 Выбор параметров и итоговые оценки

Заключение

Список цитированной литературы

Список работ автора по теме диссертации

Введение

Настоящая диссертационная работа посвящена исследованию одной из классических задач комбинаторного анализа - проблеме Эрдеша-Хайнала о раскрасках гиперграфов. Сначала напомним некоторые определения из теории графов и гиперграфов.

Гиперграфом Н называется пара Н = (V, Е), где V — некоторое конечное множество, называемое множеством вершин гиперграфа, а Е - некоторая совокупность различных подмножеств множества V, которые называются ребрами гиперграфа. Раскраской множества вершин V называется отображение ] из V в С, где С — произвольное множество (множество цветов). Если |С| = г, то раскраска называется г-цветной. Раскраска вершин гиперграфа называется правильной, если в этой раскраске все ребра гиперграфа являются неодноцвет-

Н

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

Изучение экстремальных задач о раскрасках гиперграфов началось в классических работах П. Эрдеша с различными соавторами в 60-70-х годах прошлого века. Типичную задачу подобного типа можно описать следующим образом: требуется найти минимально возможное значение определенной характеристики (числа ребер, максимальной степени вершины и т.п.) гиперграфа в

п

систем Штейнера или гиперграфов с большим обхватом) с хроматическим чис-

гг тов). Самой известной задачей из данного класса являгтея проблема Эрдеша-Хайнала: требуется найти минимально возможное количество ребер гиперграфа

пг экстремальную величину принято обозначать через т(п,г). Проблема Эрдеша^ Хайнала о величине т(п, г) — это, несомненно, одна из центральных задач тео-

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

С вычислительной точки проблема возможности правильной раскраски гиперграфа в заданное число цветов являгтея NP-полной, в связи с этим, гетг-ственным образом, возник вопрос о нахождении легко проверяемых достаточных условий r-раскрашиваемости гиперграфа. Одно из таких простых условий и изучается в задаче Эрдеша-Хайнала, ведь смысл величины m(n,r) совершенно ясен: если у n-одпородиого гиперграфа мало ребер, меньше чем m(n,r), то тогда и хроматическое число должно не превосходить т. Задача Эрдеша-Хайнала является классической, ей посвящены работы таких классиков комбинаторики, как Н. Ал он, Л. Ловас, Й. Бек, Дж. Спенсер и П. Сеймур. В последнее десятилетие был получен ряд очень сильных (как технически, так и идейно) результатов в проблеме Эрдеша-Хайнала и смежных с ней вопросах. Среди математиков, работавших в данной задаче в 2000-2017-е годы, отметим имена Дж. Радхакришнана, А. Сринивасана, A.B. Косточки, А. Плухара, Д.А. Шабанова, X. Гебауэр, Я. Козика и Д.Д. Черкашина. Были предложены качественно новые методы и вероятностные техники, позволившие и существенно продвинуться в решении данной проблемы. По сути, можно говорить о том, что произошел настоящий прорыв в данной области математики.

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

Важно отметить, что отличительной чертой задачи Эрдеша-Хайнала является тот факт, что изучение ее и ряда близких проблем стало катализатором развития вероятностных методов в дискретной математике. Был создан целый ряд вероятностных инструментов, таких, например, как Локальная лемма, которые в дальнейшем нашли применения в различных областях, но впервые были при-

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

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

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

Введение диссертации (часть автореферата) на тему «Задача Эрдеша-Хайнала о раскрасках гиперграфов и смежные вопросы»

Цель работы

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

• асимптотическое исследование проблемы Эрдеша-Хайнала о раскрасках гиперграфов;

•

максимальной степенью ребра ("локальный" вариант проблемы Эрдгша Хайнала);

породного гиперграфа.

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

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

1. Получены новые оценки в задаче Эрдеша-Хайнала о минимальном числе ребер гиперграфа в классе п-однородных гиперграфов с хроматическим числом больше г в случае, когда г > п.

2. Получены новые оценки максимальной степени ребра п-однородного гиперграфа с хроматическим числом больше г в случае, когда г > п.

3. Найдена новая нижняя оценка числа ребер 3-однородного гиперграфа с хроматическим числом больше трех.

4. Доказана теорема типа Хайнала-Семереди, дающая достаточное условие существования справедливой раскраски простого однородного гиперграфа в два цвета в терминах ограничения на максимальную степень вершины.

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

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

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

Диссертация носит теоретический характер. Результаты и методы работы могут быть полезны в исследованиях задач экстремальной и вероятностной комбинаторики, связанных с раскрасками гиперграфов. Они могут быть интересны специалистам, работающим в МФТИ, МГУ имени М.В.Ломоносова, МИРАН им. В.А. Стеклова, I II II II I РАН им. A.A. Харкевича, I II IV ВШЭ и других высших учебных заведениях и научных центрах страны.

Апробация результатов

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

1. "Кафедральный научно-исследовательский семинар кафедры дискретной математики" ФИ ВТ МФТИ, руководитель - профессор A.M. Райгородский (октябрь 2014).

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

1. 54-я научная конференции МФТИ (Долгопрудный, 10-30 ноября 2011 года).

2. 55-я научная конференции МФТИ (19 25 ноября 2012 года).

3. 57-я научная конференция МФТИ, посвященная 120-летию со дня рождения П. Л. Капицы (Долгопрудный, 24-29 ноября 2014 года).

4. European Conference on Combinatorics, Graph Theory and Applications (Eurocomb-2015, Берген, Норвегия, 31 августа - 04 сентября 2015 года).

5. Workshop on Extremal Combinatorics and Combinatorial Geometry (Долгопрудный, 25 марта 2016 года).

Публикации

Результаты диссертации опубликованы в работах [А01]-[А04] списка литературы. Всего по теме диссертации опубликовано 4 работы, из которых две в соавторстве.

Структура работы

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

Глава 1

Асимптотическое исследование задачи Эрдеша-Хайнала

Данная глава посвящена классической задаче Эрдеша-Хайнала о раскрасках гиперграфов. Результаты главы опубликованы в работах [А01], [А02].

1.1 История задачи Эрдеша-Хайнала

Проблема Эрдеша-Хайнала является одной из центральных в теории раскрасок гиперграфов. Напомним сначала основные определения.

Гиперграфом в дискретной математике называется пара Н = (V, Е), где V _ эт0 нек0Т0р0е конечное множество, называемое множеством вершин гиперграфа, а Е - это совокупность подмножеств множества V, которые принято называть ребрами гиперграфа. Гиперграф является и-однородным, если каждое его ребро содержит ровно и вершин. В частности, 2-однородный гиперграф _ эт0 в точности обычный граф.

Раскраской вершин гиперграфа Н = (V, Е) называется отображение / : V ^ N Раскраска / является правильной для Н, если в ней нет одноцветных ребер из множества Е. Гиперграф называется т-раскрашиваемым, если существует правильная раскраска его вершин в т цветов. Наконец, хроматическим числом гипеграфа Н, х(Н), называется такое минимальное т, что Н является т

Н

В 1961 П. Эрдеш и А. Хайнал [1] поставили следующую задачу: найти величину т(п, т), равную минимально возможному числу ребер в и-однородном

т

т(п,т) = шт{|Е| : Н = (V, Е) - п-однородный, х(Н) > т}.

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

Действительно, если рассмотреть полный п-однородный гиперграф па г(п — 1) + 1 вершинах, то в любой его раскраске в г цветов найдется одноцветное ребро, т.е. хроматическое число такого гиперграфа строго больше г. Следовательно, число его ребер, равное правой части (1.1), дает верхнюю оценку для т(п, г).

В случае графов, т.е. п = 2, задача легко решается и оценка (1.1) является точной. Однако, как показал Эрдеш в 1963-64гг. (см. [2, 3]), для гиперграфов величина т(п,г) имеет совершенно иное асимптотическое поведение. Например, используя вероятностный подход, он обосновал следующие оценки т(п, 2):

Заметим, что верхняя оценка Эрдеша значительно меньше, чем оценка

предоставляемая (1.1).

Аналогичные оценки т(п,г) в случае произвольного числа цветов имеют следующий вид (доказательство см. [4]):

Улучшение классических оценок Эрдеша (1.3) для величины т(п,г) происходило в течение многих десятилетий различными авторами, читателю рекомендуется ознакомиться с обзорами [4] и [5].

Исторически наиболее интересным случаем являлся случай двух цветов. Относительно него Эрдешем и Ловасом в 1973 году были выдвинуты две гипотезы. Первая из них предполагала, что величина т(п, 2) растет быстрее, чем 2П при п ^ го. Вторая, более сильная, утверждала, что т(п, 2) имеет порядок роста равный п • 2п. Первая гипотеза была доказана Й. Беком в 1977 году [6], а в следующем году Бек получил [7] сильную нижнюю оценку величины т(п, 2):

(1.1)

(1.2)

(1.3)

(1.4)

Следующего улучшгния нижней оценки пришлось ждать более 20 лет, только в 2000 году Дж. Радхакришнан и А. Сринивасан [8] усилили результат Бека (1.4), показав, что выполняется соотношение

™(п' 2) = Ч (1ПГП)2 2"). (1'5)

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

В случае г > 2 было получено более значительное число интересных результатов. Первая попытка обобщения оценки Радхакришнана и Сринивасана (1.5) для т(п, 2) на случай большего числа цветов была предпринята А.В. Косточкой [9] в 2004 году. Он показал, что при г < у71/81п((1пп)/2) выполняется неравенство

(п ) 11оВ2 г\

П \ ^2 г| + 1 1 , ,

---г" 1. (1.6)

1п П

г

П

А. Плухаром [10] в 2009 году, где он обосновал нижнюю оценку следующего вида:

т(п, г) ^ п1/2-1/2ггп-1. (1.7)

л/4пе

Неравенство (1.7) было усилено Шабановым [11] в 2012 году, который пока-г > 2

т(п,г) ^ 1 п1/2гп-1. (1.8)

2

Заметим, что оценка (1.8) улучшает результат (1.6) при г = 3, но дает более слабую асимптотическую оценку, например, при г = 4. Правда, в отличие от

г > 2

Наконец, полное обобщение результата Радхакришнана-Сринивасана (1.5) было найдено Д.Д. Черкашиным и Я. Козиком [12] в 2015 году. Им удалось

пг

™(п-г) = ^(1ПП^) ^г"-1) . (1-9)

Она асимптотически улучшает все предыдущие оценки (1.6), (1.7), (1.8

В диссертационной работе задача Эрдеша-Хайнала изучается в случае, когда значение параметра числа цветов г значительно превышает значение параметра однородности п. Для понимания особенности данной асимптотической области, сравним имеющиеся верхние оценки (1.1) и (1.3) величины т(п,г) при фиксированном п и растущем г. Простая верхняя оценка (1.1) будет иметь порядок Оп(гп), в то время как оценка (1.3), получаемая с помощью простого вероятностного метода имеет порядок роста Оп(гп 1пг). Значит, при очень болылих г первая оценка будет сильнее, более того, для графов она дает точный ответ. В связи с данным наблюдением, Эрдеш выдвинул гипотезу [13] о том, что при всех достаточно больших г > го(п) простая оценка (1.1) также является точной.

Данное предположение было опровергнуто Н. Алоном [14] для почти всех п ^ 3, который обосновал следующее неравенство:

, ч (гп\ 1п п 1 „ .

т(п,т) ^__. (1.10)

\П/ 1п п — 1 |_п/ 1п п]

Легко проверить, что отношение правой части (1.10) к правой части (1.1) при фиксированном п ^ 13 и г ^ го стремится к некоторому числу из (0,1). Тем самым, гипотеза точно не верна для всех п ^ 13.

Если же рассмотреть ситуацию, когда г = г (п) есть функция от п, растущая быстрее, чем п, т.е. г/п ^ го при п ^ го, то и оценку (1.10) можно заметно усилить, что и было сделано самим Алоном в [14], где он показал, что в подобных условиях выполняется асимптотическое соотношение:

т(п,г) = О (п5/2(1пп)(5)" (г(п —п1) + 1

n

= 0(^n2(lnn) (^J rnJ . (1.11)

Действительно, несложно понять, что оценка (1.11) улучшает ПредЬ1дущуЮ (1.10).

Итак, при фиксированном n и растущем r величина m(n,r) имеет порядок роста не более rn. Отметим, однако, что все приведенные к настоящему моменту нижние оценки (1.3), (1.6), (1.7), (1.8) и (1.9) в изучаемой ситуации имеют порядок роста rn-1. Какой же порядок правильный? Как показал Алон, m(n, r)

rn

нижняя оценка:

m(n, r) > (n — 1)

-r - n — 1

— -r

n n

n1

(1.12)

которая при г > п имеет порядок роста ^(гп). Результат (1.12) был усилен Шабановым в работе [15]. Он показал, что при г > п выполнено соотношение

т(п, г) = П (п1/2гп) . (1.13)

Одной из целей настоящей работы являгтея улучшение ранее известных оце-

г > п

1.2 Новые результаты в проблеме Эрдеша-Хайнала

Первый результат диссертационной работы улучшает верхнюю оценку (1.11) величины т(п,г).

Теорема 1.1. Пусть г > п, тогда

т(п, г) = О^п7/2(1пп)^ + ^ = О (п3(1пп)гп) . (1.14)

Улучшение по сравнению с оценкой (1.11) очевидно. Кроме того, наша оценка (1.14) улучшает и верхнюю оценку из (1.3) при условии 1пг = ^(п 1пп).

Второй результат первой главы дает новую нижнюю оценку величины т(п,г) при г > п.

Теорема 1.2. Пусть г > п ^ 3, а = |_п-1 г], Ь = г — а = |П] • Тогда, существует такая абсолютная константа с > 0, что

П

m(n,r) ^ c (п — 1)м--) ° an—1

Vln п/

1п п

В качестве мгновенного следствия мы получаем усиление результата (1.13) в п1/2/ 1п п раз.

с1 > 0

г > п выполнено

m(n,r) ^ cW г-^ ) rn. (1.15)

Mn п/

В работе [14] Алон выдвинул сильную гипотезу о том, что для любого n > 2

существует предел отношения значения m(n, r) к rn при r ^ то, lim та(?П'г) • Наготе r

ши новые оценки (1.14) и (1.15) дают полиномиальные ограничения на этот потенциальный предел:

n . m(n,r) m(n,r)

Г \ 1 1- I I ü\l I I „ о.

c • --^ lim ini-^ lim sup-^ C • n3 ln n.

ln n r^TO rn r—>-oo rn

1.3 Локальный вариант задачи Эрдеша-Хайнала

В классической задаче Эрдеша-Хайнала изучается вопрос об оценке числа ребер в однородном гиперграфе с большим хроматическим числом. В 1973 году П. Эрдеш и Л. Ловас [16] предложили следующий локальный вариант проблемы Эрдеша-Хайнала. А именно, рассмотрим величину ((п,г), равную минимально возможному значению максимальной степени ребра в п-одпородиом гиперграфе с хроматическим числом большим г. Напомним, что степенью ребра е в гиперграфе Н = (V, Е) называется число других ребер из Е, имеющих с е общие вершины. Максимальную степень ребра в гиперграфе Н обозначим через В(Н).

Первая нетривиальная нижняя оценка величины ((п, г) была получена самими Эрдешем и Ловасом в работе [16]. Они показали, что выполняется следующее неравенство:

((п,г) ^ 1 гп—1. (1.16)

В дальнейшем данная оценка была неоднократно улучшена. В частном случае двух цветов Радхакришнан и Сринивасан (см. [8]) обосновали соотношение

Первое обобщение оценки (1.17) на случай r > 2 было получено A.B. Косточкой, М. Кумбхатом и В. Рёдлем в 2010 году в работе [17]. Они показали, что если n достаточно велико по сравнению с r, n > n0(r), то

М \ ^ -4r2 ( n W(«+!) п_ 1

d(n,r) ^ e 4r ---rn 1,

Mn nJ

где a = [log2 rJ. Более сильное обобщение результата (1.17) было недавно найдено Козиком и Черкашиным в [12], где они установили соотношение

d(n,r) > ^(уП5^) ' r"-2) . (1.18

Последняя оценка остается наилучшей нижней асимптотической оценкой для d(n, r) в случае, когда значение параметра r невелико по отношению к значению параметра n. В обратной ситуации легко заметить, что оценка (1.18) становится хуже даже классического результата Эрдеша и Ловаса (1.16). Тем самым, снова, как и в случае обычной задачи Эрдеша-Хайнала о величине m(n,r), в локальной проблеме случай большого числа цветов имеет свою специфику. При

r > n ^ 3 наилучшая предыдущая нижняя оценка d(n, r) была обоснована Шабановым в его работе [11]:

d(n,r) > 1 n1/2rn-1. 8

В диссертационной работе получена новая нижняя оценка величины d(n,r), сформулированная в следующей теореме.

Теорема 1.3. Существует такая абсолютная константа c > 0, что для, любых n ^ 3 и r ^ 2 выполнено неравенство

r-1

d(n, r) ^ с(т^) r rn-1. (1.19)

Vin n/

Поймем, что означает результат теоремы 1.3. Во-первых, оценка Черкашина и Козика (1.18) улучшена в r раз, а во-вторых, при r > n мы имеем следующее соотношение, схожее с оценкой (1.15) величины m(n,r):

d(n,r) = ft(. in n

Последним результатом первой главы являгтея новая верхняя оценка величины d(n, r).

Теорема 1.4. Если r > n, mo

d(n,r) = O (n3rn-1 in n) . (1.20)

Заметим, что с помощью рассмотрения случайного гиперграфа следуя рассуждениям Эрдеша из [3], можно показать, что выполнено следующее ограничение на величину d(n,r):

d(n,r) = O (n2rn-1 in r) . (1.21)

rn

но, если in r = in n).

Оставшиеся параграфы первой главы будут посвящены доказательствам новых результатов в проблеме Эрдеша-Хайнала и ее локальном варианте.

1.4 Доказательства оценок в проблеме Эрдеша-Хайнала

В данном параграфе мы докажем оценки величины т(п, г) в задаче Эрдеша^ Хайнала для случая, когда число цветов г превосходит степень однородности п. Мы начнем с доказательства теоремы 1.2.

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

Доказательство теоремы представляет собой комбинацию идей из работ Ало-на [14] и Черкашина-Козика [12]. Пусть H = (V, E) - n-одиородпый гиперграф с числом ребер

д-1

|E| ^ c(n — 1 )b(-^) д an—i, (1.22)

Vin nJ

где a = |_r J и b = r — a = \П]. Мы хотим показать, что в этом случае гиперграф H будет являться r-раскрашиваемым.

r

пользуемся критерием, сформулированным А. Плухаром в работе [10]. Пусть | V | = Ж и а : V —^ {1,..., N} определяет порядок вершин гиперграфа H. Упорядоченный кортеж ребер (Ai,..., Ar) образует упорядоченную r-цепь по отношению к а, если для всех j = 1,... ,r — 1 выполнено

• \Aj П Aj+i | = 1,

• а(v) ^ a(u) для всех v G Aj, u G Aj+i.

Из определения следует, что последняя относительно а вершина ребра Aj является первой вершиной ребра Aj+i. Таким образом, ребра, не являющиеся соседними, не имеют общих вершин.

Следующее утверждение (называемое критерием Плухара) связывает суще-

r

r

r

только тогда, когда существует нумерация его вершин, не содержащая упо-r

Обозначим (Xv, v G V) множество независимых равномерно распределенных на [0,1] случайных величин. Для каждого ребра A G E введем следующую ве-

f (A) = min Xv, l(A) = max Xv.

vGA vGA

Пусть p = ^Ip G (0,1) Назовем ребро A плохим если выполнено следующее событие:

B(A) = { l(A) — f (A) < !—в}.

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

Плухара мы хотим показать, что Н' с положительной вероятностью является а-раскрашиваемым. Рассмотрим случайную нумерацию вершин а, индуцированную случайными величинами Х^: порядковый номер вершины V равен а(-у) = I{Хю ' Ху}. Здесь I{2} - случайная величина, являющаяся ин-

дикатором события т.е. I{2} = 1, когда имеет место 2 и 0 иначе.

Предположим, что множество хороших ребер (Л15..., Ла) образует упорядоченную а-цепь относительно нумерации а. Обозначим через V общую вершину ребер Лг и Лг+1. При фиксированных значениях Хщ = хг, г = 1,...,а — 1, XI < Хг+1 условная вероятность того, что данные ребра образуют упорядоченную а-цепь, равна

хП—1(х2 — Х1)П—2 . . . (Ха—1 — Ха—2)П—2(1 — Ха—1)П—1

Кроме того, условие, что все ребра должны быть хорошими, накладывает до-

Х1, . . . , Ха—1

^ 1 — Р ^ 1 — Р ■ 1 о / 1 1 — Р

х1 >-, хг+1 — хг >-, г = 1,..., а — 2, ха_ 1 < 1--.

а а а

Заметим, что из условия г > п > 2 следует, что а = |_г] ^ 2.

Обозначим через С(Л1,..., Ла) событие, состоящее в том, что все ребра Л^-являются хорошими и последовательность ребер (Л15..., Ла) образует упорядоченную г-цепь относительно а. Тогда вероятность этого события можно оценить следующим образом:

Р (С (Л1,...,Ла)) ' I хП—1^х1 > X

[0,1]а-1

X П ((хг — хг—1)п—2^хг — хг—1 > X

X (1 — ха—1)П—1^ха—1 < 1 — ""О^! ^х! . . . ^а—1 ' (сделаем замену: аг = хг — хг—1 — , г = 2,..., а — 1, а1 = х1 — )

<1® ) Н^+р—§ -Гх

х I < а^- > 0, ^ = 1,..., а — 1; ^^ а^- < р > ... ¿аа—1 =

а— 1

(вынесем множитель 1/а из каждой скобки)

» /а-1 \ п-2 / а-1 \ п-2

/ П(1 + - Р) • 1 + (а - 1)Р - а^аг ) х

1 \ а(п-2)

а у

[0,1]а-1

а-1

х / < а > 0, ^ = 1,..., а - 1; ^^ а < р > ... ¿аа-1 ^ (т.к. 1 + X ^ 6х)

а(п-2)

(1 \ а(п — 2) / а 1 а 1

а I ехр < (п - 2) ^ (ааг - р) + (а - 1)р - а ^ аг I ^ х

а I \г=1 г=1

а

( а-1 1

х / < а^- > 0, ^ = 1,..., а - 1; ^^ а < р > ... ¿аа-1 =

а(п-2) Г ( а-1 ^

I / / < а^- > 0, ^ = 1,..., а - 1; ^^ а^- < р > ^а1... ¿аа-1 =

[од]а-1 ^

/. ч а(п-2) ра-1 а /1 \а(п-1)

=( э с^ * з( а) ра-1ба. (1-2з)

В силу того, что а ^ 2, последний переход обоснован применением неравенств (а - 1)! > а-1 Та)а \/2Ла > 3а-1(а/е)а.

Как много упорядоченных кортежей ребер (А15..., Аа) в гиперграфе Н могут образовьтать упорядоченные г-цепи? Неупорядоченное множество может быть выбрано ^ способами и для каждого такого множества существует не более

а

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

В итоге,

Р (х(Н') > а) ^ £ Р (С (А ,...,Аа)) ^

(А1,...,Аа) могут

а

V а / 3\ а 3 а! \а/

т.к. а! > 3(а/е)а

' 2т |е |а( а)ап ра—1е2а'

по условию (1.22))

2 а—1 / 1 \ ап

' уса((п — 1)6)ааа(п—^ (^Пп) ( а ) ра—1е2а '

(используем соотношения р = (21п п)/п и (п — 1)6 < 2г при г > п

' (т)(< (т Н'-

Последнее неравенство выполняется в силу того, что а = г — 6 > г/2. Далее, устанавливая с = 1/(16е2), мы получаем из (1.24), что вероятность того, что случайный гиперграф Н' не является а-раскрашиваемым, не превосходит 1/3.

Н

ХХ

ЕХ = Р(Л - плохое ребро) = ^ Р (/(Л) — /(Л) ' 1—р ] =

= 1*1 П )" + п (^)П—1 (1 — ^)) ' |2п (рГ '

(по условию (1.22))

(1.25)

а— 1

' 2сп(п — 1)6 ( -ПМ а (1 — р)п—1 ' 2сп2(п — 1)6е—рп(1 — р)—1 ' 1п п

(т.к. р = 21п п/п < 3/4 при п ^ 3)

' 8сп2(п — 1)6е—21пп = 8с(п — 1)6 < 1 (п — 1)6

3

при с = 1/(16е2). Таким образом,

ЕХ 1

Р (Х > (п —1)6) ' (пЕТГ)6< 1

Произведем финальные рассуждения. Мы показали, что с вероятностью не менее 1/3 следующие два события происходят одновременно:

Зафиксируем правильную раскраску Н' в а цветов {1, 2,..., а}. Тогда только плохие ребра могут оказаться одноцветными в гиперграфе Н. Их количество не превосходит (п — 1)6, выберем по одной вершине из каждого из них. Обозначим эти вершины за VI,..., 'Уш, при этом т < (п — 1)6. Перекрасим каждую из этих вершин в оставшиеся цвета {а + 1,..., г} (их количество в точности равно Ь) по следующему правилу:

• вершины VI,...,уп—1 перекрашиваются в цвет а + 1,

• вершины ..., '2(п—1) перекрашиваются в цвет а + 2,...,

• вершины V(j—1)п+1,... ,Vj(п—1) перекрашиваются в цвет а + ] и т.д.

По окончании процесса перекраски все одноцветные ребра перестанут быть

(п — 1)

раза, поэтому новых одноцветных ребер не появится. Следовательно, получится

Нг

1.4.2 Верхняя оценка, доказательство теоремы 1.1

Подход Алона (см. [14]) к оценке т(п,г), упомянутый ранее, использует тесную связь между величиной т(п,г) и числами Турана. Напомним, что числом Тура,на Т (V, Ь, п) называется минимально возможное число ребер в таком п-однородном гиперграфе па V вершинах, что любое его подмножество вершин Ь

дующее соотношение между т(п,г) и числами Турана:

Ьп (г(Ь — 1) + 1) г

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

Тем самым, верхняя оценка в задаче Эрдеша-Хайнала может быть получена с помощью анализа верхних оценок чисел Турана. Лучшие из них получаются применением соотношения

X < (п — 1)Ь и х(Н') < а.

т(п, г) ^ тт Т(г(Ь — 1) + 1, Ь, п).

Ь^н

(1.26)

(1.27)

где t(b,n) - так называемая Турановская плотность, определенная следующим образом:

t(b,n)= lim ' ;.

™ и

В своем доказательстве Алой использовал верхнюю оценку для t(b,n), полученную П. Франклом и В. Рёдлем в 1985 году (см. [18]): если величина b — n является константной и n ^ то, то

< (b — n)(b — n + 4 + o(l))lnn

t(b, n) ^ / n ч •

U—J

Однако, спустя 12 лет А. Сидоренко модифицировал их конструкцию и установил новую оценку Турановской плотности [19]: если b ^ n + n/ log2 n, то

—

t(b, n) ^-^-—при n ^ то. (1.28

(1 + о(1))(Ь—п + 1)1п (")

С)

Объединяя соотношения (1.27) и (1.28) мы получаем, что существует такая абсолютная константа С > 0, что для люб ого V > Ь ^ п + п/ 1og2 п,

Ь 1п (")

т ^Дп) ' у. (1.29)

Оценим порядок роста правой части выражения (1.29) при V = г(Ь — 1) + 1. По условию, г > пи Ь > п, значит, г(Ь — 1) > п2, и мы получаем, что

(г(Ь -1) +1) = О (А (г(Ь — 1) +1)") = о (СЬ)" (Ь—1.)") = о((гЬ)")

n ) \n! ) \n!\ b ) ) \n!y

(1.30)

Далее,

bn bnn! , / n\—n ^ ^-- ^ n! 1 - - <

О " (b — n)^ Г b

(т.к. 1 — x ^ e— i-1® при x G (0,1))

< n! e^. (1.31)

Наконец,

ln( n) < ln bn = n ln b. (1.32)

В итоге, из соотношений (1.26), (1.30), (1.31) и (1.32) следует, что при r > n,

m(n,r) = O( min b(n ln b)eb-n r

Vb^n+n/ log2 n /

n2

Легко видеть, что минимальный порядок роста выражения b(ln b)eb-n достигается при b = n2. Полагая b = n2 получаем итоговый результат: при r > n

m(n,r) = O (n3(lnn)rn) .

Чтобы установить первую оценку в формулировке теоремы 1.1, m(n, r) = O (V/2(ln n)(i)" ^(n -nX) + ^ , достаточно заметить, что при r > n,

см'+ч O Ьyv, ni = O /yn\

(.(n-1,+1) = nn = ^enj

b

1.5 Доказательства оценок в локальном варианте проблемы Эрдеша-Хайнала

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

1.5.1 Нижняя оценка d(n,r), доказательство теоремы 1.3

Пусть H = (V, E) - n-однородный гиперграф и

r-1

D(H) ^ r rn-1. (1.33)

ln n

H r r

n

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

иг'

Рассмотрим множество независимых случайных величин {Xv ,v £ V} равномерно распределенных на [0,1] и индуцированный ими случайный порядок а на множестве V. Для каждого ребра A £ E, обозначим

f (A) = min Xv, l(A) = max Xv.

v£A v£A

Для заданного p £ (0,1), введем событие, означающее, что ребро A - плохое:

1 — p]

B(A) = l(A) — f(A) ^

r

Мы хотим показать, что с положительной вероятностью Н не содержит плохих ребер и гиперграф, образованный хорошими ребрами раскрашивается в г цветов. Согласно критерию Плухара, достаточно показать, что хорошие ребра не образуют упорядоченных г-цепей относительно случайной нумерации а. Таким образом, существует два типа событий, которых мы хотим избежать: В(А) и

С(А1,..., Аг), означающее, что ребра А1,..., Аг являются хорошими и образу-

г

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

Лемма 1.1. (Локальная лемма Ловаса, несимметричный вариант) Пусть А1,..., Ам - события на некотором вероятностном пространстве. Предположим, что для, каждого % = 1,..., М, выделено подмножество Si из = {1,...,М} такое, что Аг независимо с алгеброй, образованной событиями {А^£ и {%})}• Если для, любого % = 1,..., М, выполнено

Е р(А-) ^ 1/4,

3£

( м_\ м

тоР\ р| АЛ ^ П (1 - 2Р(А)) > 0.

\^=1 / 3=1

Лемма 1.2. (Локальная лемма Ловаса, полиномиальный вариант) Пусть Х1,..., Х^ - независимые случайные величины и А1,..., Ам - события из

алгебры, образованной ими. Для любого ] = 1,..., М, обозначим за у1п(А]) минимальное подмножество случайных величин Х,И которые определяют событие А] (т.е. А] принадлежит алгебре, образованной случайными величинами Xi Е у1п(А])). Обозначим через и>г(х), % = 1,..., N, многочлен следующего вида:

wг(z) = ^ ?(А)г1 vln(A)|.

А:Х^1п(А)

Пусть многочлен — удовлетворяет уеловию ) ^ — ^) для, любого % = 1,..., N и z ^ 1. Если существует, та,кое т Е (0,1), что

ЧгЪ) ^т,

/м_ \

шМ =1 АЛ > 0.

Обе формулировки выводятся из общего случая Локальной леммы Ловаса (см. [20]) в работах [8], [21]. Теперь применим Локальную лемму к нашему множеству событий.

Случай 1. Пусть г ^ 1п п. В этом случае мы будем использовать лемму 1.1. Наше множество событий состоит из В (А) и С (А\,..., Аг). Обозначим через Ф множество всех таких событий. Для каждого Q Е Ф мы выберем систему Фд такую, что д и алгебра, образованная Ф \ (Фд и {д}), независимы. Более того,

Е ) ^ 1/4. (1-34)

^еФеи{д}

Для д Е Ф обозначим через Ь(д) следующее множество вершин:

\ А, если д = В(А),

д) = <

[Аг и ... и Аг, если д = С (АЬ...,АГ).

д

ми {Х^ : V Е Ь(д)}. Таким образом, достаточно положить

Фд = {д Е Ф: ¿(¿>) П ¿(д) = 0}.

Нам остается показать истинность (1.34). Обозначим й = Б(Н), тогда, согласно, (1.23) и (1.25), для произвольного 2 Е Е(Н) выполняется следующее неравенство:

Е Р(^) < Е Р(В(А))+ Е Р(С(АЬ...,АГ)) <

^=0 А: АПИ=0 (Л1,...,Лг):

/1 _ p\ n—1 r r(n-1) < (d + 1)2n(—+ r(d + 1)dr—1 ^ -J Pr-1er. (1-35)

Прокомментируем последний переход. Ребро, пересекающее Z может быть выбрано не более, чем d + 1 способом и его позиция в цепи - r способами. Оставшиеся ребра цепи могут быть выбраны не более, чем dr-1 способами. Количество ребер, определяющих любое событие из Ф не превосходит r, поэтому для каждого Q G Ф выполнено

_ n—1 r /i\ r(n-1) r i (d + 1)2n i j + r(d + 1)dr-1 3 f ■ ) pr-1e

JG^:

L(J )nL(Q)=0

E P(J) ^ 4 (d + 1)2nf P^

Je^: V V r /

Согласно (1.33),

( n )(r—1)/r n !

d < c ---rn-1

Vin n/

и положим p = . Тогда

E p(J) < 4r(dn( JG^: V ^

1 p\ n—1 r /1 \ r(n-1)

+ rdr - -) pr—1 er I <

. r / 3 V r

JG^:

L(J )nL(Q)=0

r — 1 2 (r—/Ol \ r —1

< 4r | cn (^) ^ e—+ ^ cr (^) ^ er 1 <

Лп n/ 3 Vin n/ \ n

< 4ecr fe—pn + 2r3(2ce)r = in n 3

(т.к. e pn = n 2)

(т.к. r ^ in n)

r2

= 4ec--+ -r3(2ec)r <

in n 3

2

< 4ec + -r3(2ec)r < 1/4 3

при малых с > 0. Например, достаточно выбрать с = убе-

Случай 2. Теперь предположим, что г > 1п п. В этом случае мы будем использовать полиномиальный вариант Локальной леммы, лемму 1.2. Легко видеть, что для любого 2 Е Ф, у1п(2) = {X« : V Е 1(2)}. Таким образом, для всех

г ^ 1,

^(г)= Е Р(^)^1 '1П(2)1 = Е Р(В(А))г|^п(в(А))| +

2ЕФ: «ЕЬ(2) А: «ЕА

+ £ Р(С(Ах,..., Аг))*1 -МС(Аь...А^

(А1,...,ЛГ):

т.к. | у1п(В(А))| = п, | ^п(С(Ах,..., Аг))| ^ гп)

< ^ Р(В(А))*П + ^ Р(С(АЬ...,АГ))*гп <

А: «еА (АЬ...,АГ):

в силу (1.23) и (1.25))

< Е ^ + Е 33 (Ю Г("-1> РГ-1еГ*™ <

А: «еА 4 У (АЬ...,АГ): 4 У

Зi «еА,

существует не более г(ё + 1)ёг-1 упорядоченных г-цепей содержащих фиксированную вершину)

2 г2

< 2п(ё + 1)г-(п-1)е-рп+1*п + — (ё + 1)ёг-1г-г(п-1)рг-1ег*гп <

3

(т.к. ё + 1 ^ 2ё)

2г2

< 4еёг-(п-1)пе-рп*п + — г-г(п-1)рг-1ег*гп = Ц*). (1.36)

3

Осталось выбрать такое т е (0,1), что уз^) ^ т. Положим

1 31п п

т =-, р =- (при условии п ^ 5 р е (0,1)).

Список литературы диссертационного исследования кандидат наук Акользин Илья Александрович, 2018 год

Список цитированной литературы

[1] 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.

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

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

[4] A.M. Raigorodskii, D.A. Sliabanov, "The Erdos - Hajnal problem of liypergrapli colouring, its generalizations and related problems", Russian Mathematical Surveys, 66:5 (2011), 933-1002.

[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] J. Beck, "On a combinatorial problem of P. Erdos and L. Lovasz", Discrete Mathematics, 17:2 (1977), 127-131.

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

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

[9] A. V. Kostochka, "Coloring uniform hypergraphs with few colors", Random, Structures and Algorithms, 24:1 (2004), 1-10.

[10] A. Pluliar, "Greedy colorings for uniform hypergraphs", Random, Structures and, Algorithms, 35:2 (2009), 216-221.

[11] D.A. Sliabanov, "On r-chromatic hypergraphs", Discrete Mathematics, 312:2 (2012), 441-458.

[12] D. Cherkashin, J. Kozik, "A note on random greedy coloring of uniform hypergraphs", Random, Structures and Algorithms, 47:3 (2015), 407-413.

[13] 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 Nurnerantium, XXIII, Utilitas Mathematica, Winnipeg, 1979, 19 37.

[14] N. Alon, "Hypergraphs with high chromatic number", Gra/phs and Combinatorics, 1:1 (1985), 387-389.

[15] Д. А. Шабанов, "Об улучшении нижней оценки в комбинаторной задаче Эрдеша-Хайнала", Доклады, Академии, Наук, 426:2 (2009), 177-178.

[16] 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.

[17] A.V. Kostochka, M. Kumbhat, V. Rodl, "Coloring uniform hypergraphs with small edge degrees". Fete of Combinatorics arid Computer Science, Bolyai Society Mathematical Studies, 20, Springer, 2010, 213-238.

[18] P. Frankl, V. Rodl, "Lower bounds for Turan's problem", Graphs arid Combinatorics, 1:1 (1985), 213-216.

[19] A. Sidorenko, "Upper bounds for Turan numbers", Journal of Combinatorial Theory, Series A, 77:1 (1997), 134-147.

[20] N. Alon, J.H. Spencer, The Probabilistic Method, 3rd Edition, Wiley, 2008.

[21] J. Beck, "A remark concerning arithmetic progressions", Journal of Combinatorial Theory, Series A, 29:3 (1980), 376-379.

[22] H. L. Abbot, L. Moser, "On a combinatorial problem of Erdos and Hajnal", Canadian Mathematical Bullettin, 7 (1964), 177-181.

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

[24] B. Toft, "On color critical hypergraphs", Infinite arid Finite Sets, 3 (1975), 1445-1457.

[25] P. D. Seymour, "A note on a combinatorial problem of Erdos and Hajnal", J. London Math. Soc., 8:2 (1974), 681-682.

[26] J. Mathews, M. K. Panda, S. Shannigrahi, "On the construction of non-2-colorable uniform hypergraphs", Discrete Applied Ma,them,a,tics, 180 (2015), 181-187.

[27] M. Goldberg, H. Russell, "Toward Computing m(4)", Ars Combinatorial 39 (1995), 139-148.

[28] G. M. Manning, "Some results on the m(4) problem of Erdos and Hajnal", Electronic Research Announcements of the American Mathematical Society, 1:3 (1995), 112-113.

[29] P. Ostergard, "On the minimum size of 4-uniform hypergraphs without property B", Discrete Applied Mathematics, 163 (2014), 199-204.

[30] A.F. Sidorenko, "What we know and what we do not know about Turan numbers", Graphs arid Combinatorics, 11 (1995), 179-199.

[31] E.D. Boyer, D.L. Krelier, S.P. Radziszowski, A.F. Sidorenko, "On (n, 5,3)-Turan systems", Ars Combinatorial 37 (1994), 13-31.

[32] P. Erdos, Problem 9 in " Theory of Graphs arid its Applications" (M. Fieldler, ed.), Czech. Acad. Sci. Publ, Prague, 1964, 159.

[33] A. Hajnal, E. Szemeredi, "Proof of a conjecture of P. Erdos", Combinatorial theory arid its applications. II (Proc. Colloq.. Balatonfured. 1969) (1970), 601623.

[34] H. Kierstead, A.V. Kostochka, "A short proof of Hajnal-Szemeredi Theorem on equitable coloring", Combinatorics. Probability arid Computing, 17:2 (2008), 265-270.

[35] H. Kierstead, A.V. Kostochka, "An Ore-type theorem on equitable coloring". Journal of Combinatorial Theory, Series Д 98:1 (2008), 226-234.

[36] H. Kierstead, A.V. Kostochka, M. Mydlarz, E. Szemeredi, "A fast algorithm for equitable coloring", Combinatorica, 30:2 (2010), 217-224.

[37] Z. Szabo, "An application of Lovasz Local Lemma - a new lower bound for the van der Waerden number", Random, Structures and Algorithms, 1:3 (1990), 343-360.

[38] A.V. Kostochka, M. Kubmhat, "Coloring uniform hypergraphs with few edges". Random, Structures and Algorithms, 35:3 (2009), 348-368.

[39] D.A. Shabanov, "Random coloring method in the combinatorial problem of Erdos and Lovasz", Random, Structures and Algorithms, 40:2 (2012), 227-253.

[40] J. Kozik, "Multipass greedy coloring of simple uniform hypergraphs". Random, Structures and Algorithms, 48:1 (2016), 125-146.

[41] А.Б. Купавский, Д.А. Шабанов, "Раскраски однородных гиперграфов с большим обхватом". Доклады, Академии Наук, 443:4 (2012), 422-426.

[42] J. Kozik, D.A. Shabanov, "Improved algorithms for colorings of simple hypergraphs and applications", Journal of Combinatorial Theory, Series Д 116 (2016), 312-332.

[43] L. Lu, L. Szekely, "Using Lovasz Local Lemma in the space of random injections", Electronic Journal of Combinatorics 13 (2007), Research paper ЛЧ)3.

[44] D.A. Shabanov, "Equitable two-colorings of uniform hypergraphs", European Journal of Combinatorics, 43 (2015), 185-203.

[45] A.V. Kostochka, V. Rodl, "Constructions of sparse uniform hypergraphs with high chromatic number" Random, Structures and Algorithms, 36:1 (2010), 4656.

Список работ автора по теме диссертации

[А01] I.A. Akolzin, D.A. Shabanov, "Colorings of liypergraplis with large number of colors", Discrete Mathematics, 339:12 (2016)^ 3020-3031.

[A02] I.A. Akolzin, D.A. Shabanov, "Colorings of liypergraplis with large number of colors", Electronic Notes in Discrete Mathematics, 49 (2015), 441-445.

[A03] И. А. Акользин, "О задаче Эрдеша-Хайнала для 3-однородных гиперграфов", Матем. заметки, 94:6 (2013), 933-935.

[А04] И. А. Акользин, "О справедливых раскрасках простых гиперграфов", Труды МФТИ, 9:4 (2017), 161-173.