Несоответствие гиперграфов

Область теории расхождений

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

Определения

В классической постановке мы стремимся разбить вершины гиперграфа на два класса таким образом, чтобы в идеале каждое гиперребро содержало одинаковое количество вершин в обоих классах. Разбиение на два класса можно представить раскраской . Мы называем −1 и +1 цветами . Цветовые классы и образуют соответствующее разбиение. Для гиперребра положим ${\displaystyle {\mathcal {H}}=(V,{\mathcal {E}})}$ ${\displaystyle \chi \colon V\rightarrow \{-1,+1\}}$ ${\displaystyle \chi ^{-1}(-1)}$ ${\displaystyle \chi ^{-1}(+1)}$ ${\displaystyle E\in {\mathcal {E}}}$

${\displaystyle \chi (E):=\sum _{v\in E}\chi (v).}$

Расхождение по отношению к ${\displaystyle {\mathcal {H}}}$ ${\displaystyle \chi }$ и расхождение ${\displaystyle {\mathcal {H}}}$ определяются как

${\displaystyle \operatorname {disc} ({\mathcal {H}},\chi ):=\;\max _{E\in {\mathcal {E}}}|\chi (E)|,}$

${\displaystyle \operatorname {disc} ({\mathcal {H}}):=\min _{\chi :V\rightarrow \{-1,+1\}}\operatorname {disc} ({\mathcal {H}},\chi ).}$

Эти понятия, а также термин «расхождение», по-видимому, впервые появились в статье Бека . ^[1] Более ранние результаты по этой проблеме включают в себя известную нижнюю границу расхождения арифметических прогрессий Рота ^[2] и верхние границы для этой проблемы и другие результаты Эрдёша и Спенсера ^{[3] [4]} и Саркёзи. ^{[5] : 39} В то время проблемы расхождения назывались квази- проблемами Рамсея .

Примеры

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

• Если все ребра пересекаются тривиально, т.е. для любых двух различных ребер , то расхождение равно нулю, если все ребра имеют четную мощность, и единице, если имеется ребро нечетной мощности. ${\displaystyle {\mathcal {H}}}$ ${\displaystyle E_{1}\cap E_{2}=\varnothing }$ ${\displaystyle E_{1},E_{2}\in {\mathcal {E}}}$
• Другая крайность отмечена полным гиперграфом . В этом случае расхождение равно . Любая 2-раскраска будет иметь цветовой класс по крайней мере этого размера, и этот набор также является ребром. С другой стороны, любая раскраска с цветовыми классами размера и доказывает, что расхождение не больше . Кажется, что расхождение отражает, насколько хаотично пересекаются гиперребра . Однако все не так просто, как показывает следующий пример. ${\displaystyle (V,2^{V})}$ ${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$ ${\displaystyle \chi }$ ${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$ ${\displaystyle \lfloor {\frac {1}{2}}|V|\rfloor }$ ${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$ ${\displaystyle {\mathcal {H}}}$
• Установите , и . Проще говоря, это гиперграф на 4 k вершинах {1,...,4 k }, все ребра которого являются подмножествами, имеющими одинаковое количество элементов в {1,...,2 k }, как и в {2 k +1,...,4 k }. Теперь имеет много (более ) сложно пересекающихся ребер. Однако его расхождение равно нулю, поскольку мы можем покрасить {1,...,2 k } в один цвет, а {2 k +1,...,4 k } в другой цвет. ${\displaystyle n=4k}$ ${\displaystyle k\in {\mathcal {N}}}$ ${\displaystyle {\mathcal {H}}_{n}=([n],\{E\subseteq [n]\mid |E\cap [2k]|=|E\setminus [2k]|\})}$ ${\displaystyle {\mathcal {H}}_{n}}$ ${\displaystyle {\mathcal {H}}_{n}}$ ${\displaystyle {\binom {n/2}{n/4}}^{2}=\Theta ({\frac {1}{n}}2^{n})}$

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

Общие гиперграфы

1. Для любого гиперграфа с n вершинами и m ребрами: ${\displaystyle {\mathcal {H}}}$

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq {\sqrt {2n\ln(2m)}}.}$

Доказательство — простое применение вероятностного метода. Пусть — случайная раскраска, т.е. имеем ${\displaystyle \chi :V\rightarrow \{-1,1\}}$

${\displaystyle \Pr(\chi (v)=-1)=\Pr(\chi (v)=1)={\frac {1}{2}}}$

независимо для всех . Так как является суммой независимых −1, 1 случайных величин. Таким образом, для всех и . Взяв, получаем ${\displaystyle v\in V}$ ${\displaystyle \chi (E)=\sum _{v\in E}\chi (v)}$ ${\displaystyle \Pr(|\chi (E)|>\lambda )<2\exp(-\lambda ^{2}/(2n))}$ ${\displaystyle E\subseteq V}$ ${\displaystyle \lambda \geq 0}$ ${\displaystyle \lambda ={\sqrt {2n\ln(2m)}}}$

${\displaystyle \Pr(\operatorname {disc} ({\mathcal {H}},\chi )>\lambda )\leq \sum _{E\in {\mathcal {E}}}\Pr(|\chi (E)|>\lambda )<1.}$

Так как случайная раскраска с положительной вероятностью имеет расхождение не более , в частности, существуют раскраски, которые имеют расхождение не более . Следовательно ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq \lambda .\ \Box }$

2. Для любого гиперграфа с n вершинами и m ребрами, такого что : ${\displaystyle {\mathcal {H}}}$ ${\displaystyle m\geq n}$

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\in O({\sqrt {n}}).}$

Чтобы доказать это, потребовался гораздо более сложный подход с использованием функции энтропии. Конечно, это особенно интересно для . В случае , может быть показано для достаточно больших n. Поэтому этот результат обычно называют «достаточно шести стандартных отклонений». Он считается одной из вех теории расхождений. Метод энтропии нашел множество других применений, например, в доказательстве жесткой верхней границы для арифметических прогрессий Матушека и Спенсера ^[6] или верхней границы в терминах функции первичного дробления Матушека. ^[7] ${\displaystyle m=O(n)}$ ${\displaystyle m=n}$ ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 6{\sqrt {n}}}$

Гиперграфы ограниченной степени

Лучшие границы расхождения могут быть достигнуты, когда гиперграф имеет ограниченную степень , то есть каждая вершина содержится не более чем в t ребрах, для некоторого малого t . В частности: ${\displaystyle {\mathcal {H}}}$

• Бек и Фиала ^[8] доказали, что ; это известно как теорема Бека–Фиалы . Они предположили, что . ${\displaystyle \operatorname {disc} ({\mathcal {H}})<2t}$ ${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t}})}$
• Беднарчак и Хельм ^[9] и Хельм ^[10] улучшили связь Бека-Фиалы небольшими шагами до (для слегка ограниченной ситуации, т. е. ). ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 2t-3}$ ${\displaystyle t\geq 3}$
• Бух ^[11] улучшил это в 2016 году до , где обозначает итеративный логарифм . ${\displaystyle 2t-\log ^{*}t}$ ${\displaystyle \log ^{*}t}$
• Следствие из статьи Бека ^[1] – где впервые в явном виде появилось понятие расхождения – показывает для некоторой константы C. ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq C{\sqrt {t\log m}}\log n}$
• Последнее улучшение в этом направлении принадлежит Банащику: ^[12] . ${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t\log n}})}$

Специальные гиперграфы

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

• Несоответствие перестановок — когда вершинами являются целые числа 1,..., n , а гиперребрами являются все интервалы некоторых m заданных перестановок на целых числах.
• Геометрическое несоответствие — когда вершины являются точками в евклидовом пространстве, а гиперребра — геометрическими объектами, такими как прямоугольники или полупространства.

• Арифметические прогрессии (Рот, Саркози, Бек , Матушек и Спенсер )
• Достаточно шести стандартных отклонений (Спенсер)

Основные открытые проблемы

• Гипотеза Комлоша ^[13]

Приложения

• Численное интегрирование: методы Монте-Карло в больших размерностях.
• Вычислительная геометрия: алгоритмы «разделяй и властвуй» .
• Обработка изображений: Полутоновая обработка

Примечания

1. J. Beck: "Оценка Рота расхождения целочисленных последовательностей почти точна", стр. 319-325. Combinatorica , 1, 1981
2. К. Ф. Рот: «Замечание относительно целочисленных последовательностей», страницы 257–260. Акта Арифметика 9, 1964 г.
3. Дж. Спенсер: «Замечание о раскраске целых чисел», страницы 43–44. Канадский математический бюллетень 15, 1972.
4. П. Эрдёш и Дж. Спенсер: «Дисбалансы в k-окрашиваниях», страницы 379–385. Networks 1, 1972.
5. П. Эрдеш и Дж. Спенсер: «Вероятностные методы в комбинаторике». Будапешт: Академия Киадо , 1974.
6. J. Matoušek и J. Spencer: «Расхождение в арифметических прогрессиях», страницы 195–204. Журнал Американского математического общества 9, 1996.
7. J. Matoušek: «Точная верхняя граница для расхождения полупространств», страницы 593–601. Discrepancy and Computational Geometry 13, 1995.
8. Дж. Бек и Т. Фиала: «Теоремы о создании целых чисел», страницы 1–8. Дискретная прикладная математика 3, 1981.
9. Д. Беднарчак и М. Хельм: «Заметка о теореме Бека-Фиалы», стр. 147–149. Combinatorica 17, 1997.
10. М. Хельм: «О теореме Бека-Фиалы», стр. 207. Дискретная математика 207, 1999.
11. Б. Бух: «Улучшение теоремы Бека–Фиалы», стр. 380–398. Комбинаторика, вероятность и вычисления 25, 2016.
12. Банащик, В. (1998), «Балансировка векторов и гауссовская мера n -мерных выпуклых тел», Случайные структуры и алгоритмы , 12: 351–360, doi :10.1002/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S.
13. Бансал, Нихил; Дадуш, Даниэль; Гарг, Шашват (январь 2019 г.). «Алгоритм для гипотезы Комлоша, соответствующий границе Банасчика». SIAM Journal on Computing . 48 (2): 534–553. doi :10.1137/17M1126795. ISSN  0097-5397.

Ссылки

• Бек, Йожеф ; Чен, Уильям В. Л. (2009). Нерегулярности распространения . Cambridge University Press. ISBN 978-0-521-09300-2.
• Шазелл, Бернард (2000). Метод расхождения: случайность и сложность . Cambridge University Press. ISBN 0-521-77093-9.
• Doerr, Benjamin (2005). Интегральное приближение (PDF) ( Докторская диссертация). Кильский университет . OCLC  255383176. Получено 20 октября 2019 г.
• Матушек, Иржи (1999). Геометрическое несоответствие: иллюстрированное руководство . Спрингер. ISBN 3-540-65528-X.