Упаковка в гиперграф

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

История

Задача нахождения числа таких подмножеств в k -однородном гиперграфе была первоначально мотивирована гипотезой Пола Эрдёша и Хаима Ханани в 1963 году. Войтех Рёдль доказал их гипотезу асимптотически при определенных условиях в 1985 году. Пиппенджер и Джоэл Спенсер обобщили результаты Рёдля, используя случайный жадный алгоритм в 1989 году.

Определения и терминология

В следующих определениях гиперграф обозначается как H =( V , E ). H называется k -однородным гиперграфом , если каждое ребро в E состоит ровно из k вершин.

П {\displaystyle P} является упаковкой гиперграфа, если она представляет собой подмножество ребер в H, такое, что не существует пары различных ребер с общей вершиной.

ЧАС {\displaystyle H} является ( , )-хорошим гиперграфом, Д 0 {\displaystyle D_{0}} ϵ {\displaystyle \epsilon} если существует такой , что для всех и и выполняются оба следующих условия. Д 0 {\displaystyle D_{0}} х , у ∈ В {\displaystyle x,y\in V} Д ≥ Д 0 {\displaystyle D\geq D_{0}}

Д ( 1 − ϵ ) ≤ градус ( х ) ≤ Д ( 1 + ϵ ) {\displaystyle D(1-\epsilon )\leq {\text{deg}}(x)\leq D(1+\epsilon )}
кодег ( х , у ) ≤ ϵ Д {\displaystyle {\text{codeg}}(x,y)\leq \epsilon D}

где степень вершины — это число ребер, содержащих и кодеспоследовательность двух различных вершин , а — это число ребер, содержащих обе вершины. градус ( х ) {\displaystyle {\text{градус}}(x)} х {\displaystyle x} х {\displaystyle x} кодег ( х , у ) {\displaystyle {\text{codeg}}(x,y)} х {\displaystyle x} у {\displaystyle y}

Теорема

Существует асимптотическая упаковка P размера не менее для -однородного гиперграфа при следующих двух условиях: н К + 1 ( 1 − о ( 1 ) ) {\displaystyle {\frac {n}{K+1}}(1-o(1))} ( К + 1 ) {\displaystyle (К+1)}

  1. Все вершины имеют степень , стремящуюся к бесконечности. Д ( 1 + о ( 1 ) ) {\displaystyle D(1+o(1))} Д {\displaystyle D}
  2. Для каждой пары вершин существуют только общие ребра. о ( Д ) {\displaystyle o(D)}

где — общее число вершин. Этот результат был показан Пиппенджером и позже доказан Джоэлом Спенсером. Для решения проблемы асимптотической упаковки гиперграфа Джоэл Спенсер предложил случайный жадный алгоритм. В этом алгоритме в качестве основы используется ветвящийся процесс, и было показано, что он почти всегда достигает асимптотически оптимальной упаковки при указанных выше побочных условиях. н {\displaystyle n}

Асимптотические алгоритмы упаковки

Существует два известных алгоритма асимптотической упаковки k-однородных гиперграфов: случайный жадный алгоритм с использованием ветвящегося процесса и отсечение Редля.

Случайный жадный алгоритм через ветвящийся процесс

Каждому ребру независимо и равномерно назначается определенное реальное «время рождения» . Ребра берутся одно за другим в порядке их времен рождения. Ребро принимается и включается в , если оно не перекрывает ни одно ранее принятое ребро. Очевидно, что подмножество является упаковкой, и можно показать, что его размер почти наверняка. Чтобы показать это, остановим процесс добавления новых ребер в момент времени . Для произвольного выберем такой, что для любого -хорошего гиперграфа , где обозначает вероятность выживания вершины (вершина выживает, если она не находится ни в одном ребре в ) до момента времени . Очевидно, что в такой ситуации ожидаемое число выживших в момент времени меньше . В результате вероятность выживания, которая меньше , больше . Другими словами, должно включать по крайней мере вершины, что означает, что . Э ∈ ЧАС {\displaystyle E\in H} т Э ∈ [ 0 , Д ] {\displaystyle t_{E}\in [0,D]} Э {\displaystyle E} П {\displaystyle P} П {\displaystyle P} | П | = н К + 1 {\displaystyle |P|={\frac {n}{K+1}}} с {\displaystyle с} γ > 0 {\displaystyle \гамма >0} с , Д 0 , ϵ {\displaystyle c,D_{0},\epsilon } ( Д 0 , ϵ ) {\displaystyle (D_{0},\epsilon)} ф х , ЧАС ( с ) < γ 2 {\displaystyle f_{x,H}(c)<\gamma ^{2}} ф х , ЧАС ( с ) {\displaystyle f_{x,H}(c)} х {\displaystyle x} П {\displaystyle P} с {\displaystyle с} х {\displaystyle x} с {\displaystyle с} γ 2 н {\displaystyle \гамма ^{2}n} х {\displaystyle x} γ н {\displaystyle \гамма n} 1 − γ {\displaystyle 1-\гамма} П с {\displaystyle P_{c}} ( 1 − γ ) н {\displaystyle (1-\гамма)n} | П | ≥ ( 1 − γ ) н К + 1 {\displaystyle |P|\geq (1-\gamma){\frac {n}{K+1}}}

Для завершения доказательства необходимо показать, что . Для этого асимптотическое поведение выживания моделируется непрерывным ветвящимся процессом. Зафиксируем и начнем с Евы с датой рождения . Предположим, что время идет назад, поэтому Ева рожает в интервале с единичной плотностью распределения Пуассона . Вероятность рождения Евы равна . При условии, что времена рождения независимо и равномерно распределены на . Каждое рождение, произведенное Евой, состоит из потомков, все с одинаковым временем рождения, скажем . Процесс повторяется для каждого потомка. Можно показать, что для всех существует , так что с вероятностью, большей, чем , у Евы будет не более потомков. лим с → ∞ лим х , ЧАС ф х , ЧАС ( с ) = 0 {\displaystyle \lim _{c\rightarrow \infty }\lim _{x,H}f_{x,H}(c)=0} х {\displaystyle x} с > 0 {\displaystyle с>0} с {\displaystyle с} [ 0 , с ) {\displaystyle [0,c)} к {\displaystyle к} е − с с к к ! {\displaystyle {\frac {e^{-c}c^{k}}{k!}}} к {\displaystyle к} х 1 , . . . , х к {\displaystyle x_{1},...,x_{k}} [ 0 , с ) {\displaystyle [0,c)} В {\displaystyle Q} а {\displaystyle а} ϵ > 0 {\displaystyle \epsilon >0} К {\displaystyle К} ( 1 − ϵ ) {\displaystyle (1-\epsilon)} К {\displaystyle К}

Корневое дерево с понятиями родителя, ребенка, корня, очередности рождения и маточного партнера будет называться деревом выводка. При наличии конечного дерева выводка мы говорим для каждой вершины, что она выживает или умирает. Вершина без детей выживает. Вершина умирает тогда и только тогда, когда у нее есть по крайней мере один выводок, все из которых выживают. Пусть обозначает вероятность того, что Ева выживет в дереве выводка, заданном вышеприведенным процессом. Цель состоит в том, чтобы показать , а затем для любого фиксированного можно показать, что . Эти два отношения завершают наше рассуждение. Т {\displaystyle Т} ф ( с ) {\displaystyle f(c)} Т {\displaystyle Т} лим с → ∞ ф ( с ) = 0 {\displaystyle \lim _ {c\rightarrow \infty} f (c) = 0} с {\displaystyle с} лим ∗ ф х , ЧАС ( с ) = ф ( с ) {\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}

Чтобы показать , пусть . Для малых, как, грубо говоря, Ева, начинающаяся в момент времени, может иметь рождение в интервале времени все дети которой выживают, в то время как Ева не имеет рождений в интервале времени все дети которой выживают. Позволяя получить дифференциальное уравнение . Начальное значение дает единственное решение . Обратите внимание, что действительно . ф ( с ) = 0 {\displaystyle f(c)=0} с ≥ 0 , Δ с > 0 {\displaystyle c\geq 0,\Delta c>0} Δ с {\displaystyle \Дельта с} ф ( с + Δ с ) − ф ( с ) ≈ − ( Δ с ) ф ( с ) В + 1 {\displaystyle f(c+\Delta c)-f(c)\approx -(\Delta c)f(c)^{Q+1}} с + Δ с {\displaystyle c+\Дельта c} [ с , с + Δ с ) {\displaystyle [c,c+\Дельта c)} [ 0 , с ) {\displaystyle [0,c)} Δ с → 0 {\displaystyle \Delta c\rightarrow 0} ф ′ ( с ) = − ф ( с ) В + 1 {\displaystyle f'(c)=-f(c)^{Q+1}} ф ( 0 ) = 1 {\displaystyle f(0)=1} ф ( с ) = ( 1 + В с ) − 1 / В {\displaystyle f(c)=(1+Qc)^{-1/Q}} лим с → ∞ ф ( с ) = 0 {\displaystyle \lim _ {c\rightarrow \infty} f (c) = 0}

Чтобы доказать , рассмотрим процедуру, которую мы называем History, которая либо прерывает, либо создает broodtree. History содержит набор вершин, изначально . будет иметь структуру broodtree с корнем. Они либо обработаны, либо не обработаны, изначально не обработан. Каждому назначается время рождения , мы инициализируем . History заключается в том, чтобы взять необработанный и обработать его следующим образом. Для значения all with но без , которое уже было обработано, если либо некоторые имеют и с , либо некоторые имеют с и , то History прерывается. В противном случае для каждого с добавить все к как wombmates с родителем и общей датой рождения . Now считается обработанным. History останавливается, если не прерывается, когда все обработаны. Если History не прерывается, то root выживает broodtree тогда и только тогда, когда выживает в момент времени . Для фиксированного broodtree пусть обозначает вероятность того, что процесс ветвления дает broodtree . Тогда вероятность того, что History не прерывается, равна . В силу конечности процесса ветвления, суммирование по всем выводным деревьям и История не прерывается. Распределение его выводного дерева приближается к распределению процесса ветвления. Таким образом , . лим ∗ ф х , ЧАС ( с ) = ф ( с ) {\displaystyle \lim ^{*}f_{x,H}(c)=f(c)} Т {\displaystyle Т} Т = { х } {\displaystyle T=\{x\}} T {\displaystyle T} x {\displaystyle x} y ∈ T {\displaystyle y\in T} x {\displaystyle x} y ∈ T {\displaystyle y\in T} t y {\displaystyle t_{y}} t x = c {\displaystyle t_{x}=c} y ∈ T {\displaystyle y\in T} t E {\displaystyle t_{E}} y ∈ E {\displaystyle y\in E} x ∈ E {\displaystyle x\in E} E {\displaystyle E} t E < t y {\displaystyle t_{E}<t_{y}} y , z ∈ E {\displaystyle y,z\in E} z ∈ T {\displaystyle z\in T} E , E ′ {\displaystyle E,E'} t E , t E ′ < t y {\displaystyle t_{E},t_{E'}<t_{y}} y ∈ E , E ′ {\displaystyle y\in E,E'} | E ∪ E ′ | > 1 {\displaystyle |E\cup E'|>1} E {\displaystyle E} t E < t y {\displaystyle t_{E}<t_{y}} z ∈ E − { y } {\displaystyle z\in E-\{y\}} T {\displaystyle T} y {\displaystyle y} t E {\displaystyle t_{E}} y {\displaystyle y} y ∈ T {\displaystyle y\in T} x {\displaystyle x} T {\displaystyle T} x {\displaystyle x} c {\displaystyle c} f ( T , c ) {\displaystyle f(T,c)} T {\displaystyle T} f ( T , c ) {\displaystyle f(T,c)} ∑ f ( T , c ) = 1 {\displaystyle \sum f(T,c)=1} T {\displaystyle T} l i m ∗ {\displaystyle lim^{*}} lim ∗ f x , H ( c ) = f ( c ) {\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}

Откусывание Rödl

В 1985 году Рёдль доказал гипотезу Пола Эрдёша методом, называемым отрывком Рёдля. Результат Рёдля можно сформулировать в виде задачи упаковки или покрытия. Для числа покрытия, обозначенного как , показан минимальный размер семейства -элементных подмножеств , обладающих свойством, что каждое -элементное множество содержится по крайней мере в одном . Гипотеза Пола Эрдёша и др. была 2 ≤ l < k < n {\displaystyle 2\leq l<k<n} M ( n , k , l ) {\displaystyle M(n,k,l)} κ {\displaystyle \kappa } k {\displaystyle k} { 1 , . . . , n } {\displaystyle \{1,...,n\}} l {\displaystyle l} A ∈ κ {\displaystyle A\in \kappa }

lim n → ∞ M ( n , k , l ) ( n l ) / ( k l ) = 1 {\displaystyle \lim _{n\rightarrow \infty }{\frac {M(n,k,l)}{{n \choose l}/{k \choose l}}}=1} .

где . Эта гипотеза грубо означает, что тактическая конфигурация асимптотически достижима. Аналогично можно определить число упаковки как максимальный размер семейства подмножеств -элементов, обладающих свойством, что каждое множество -элементов содержится не более чем в одном . 2 ≤ l < k {\displaystyle 2\leq l<k} m ( n , k , l ) {\displaystyle m(n,k,l)} κ {\displaystyle \kappa } k {\displaystyle k} { 1 , . . . , n } {\displaystyle \{1,...,n\}} l {\displaystyle l} A ∈ κ {\displaystyle A\in \kappa }

Упаковка в более жестких условиях

В 1997 году Нога Алон , Чжон Хан Ким и Джоэл Спенсер также предложили хорошую границу для при более сильном условии кодовой степени, что каждая различимая пара имеет не более одного общего ребра. γ {\displaystyle \gamma } v , v ′ ∈ V {\displaystyle v,v'\in V}

Для k -однородного, D -регулярного гиперграфа на n вершинах, если k > 3, существует упаковка P, покрывающая все вершины, но не более . Если k = 3, существует упаковка P, покрывающая все вершины, но не более . O ( n D − 1 / ( k − 1 ) ) {\displaystyle O(nD^{-1/(k-1)})} O ( n D − 1 / 2 ln 3 / 2 ⁡ D ) {\displaystyle O(nD^{-1/2}\ln ^{3/2}D)}

Эта граница желательна в различных приложениях, таких как система троек Штейнера . Система троек Штейнера — это 3-однородный, простой гиперграф, в котором каждая пара вершин содержится ровно в одном ребре. Поскольку система троек Штейнера, очевидно, d =( n -1)/2-регулярна, указанная выше граница обеспечивает следующее асимптотическое улучшение.

Любая система троек Штейнера на n вершинах содержит упаковку, покрывающую все вершины, но не более . O ( n 1 / 2 ln 3 / 2 ⁡ n ) {\displaystyle O(n^{1/2}\ln ^{3/2}n)}

Впоследствии это улучшилось до [1] и [2]. n / 3 − O ( log ⁡ n log ⁡ log ⁡ n ) {\displaystyle n/3-O({\frac {\log n}{\log \log n}})} n − 4 3 {\displaystyle {\frac {n-4}{3}}}

Смотрите также

Ссылки

  1. ^ Киваш, Питер ; Покровский, Алексей; Судаков, Бенни ; Епремян, Лиана (2022-04-15). «Новые границы для гипотезы Райзера и связанные с ней проблемы». Труды Американского математического общества, серия B. 9 ( 8): 288–321. doi : 10.1090/btran/92 . hdl : 20.500.11850/592212 . ISSN  2330-0000.
  2. ^ Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n ». arXiv : 2310.19779 [math.CO].
  • Эрдеш, П .; Ханани, Х. (2022), «О предельной теореме комбинаторного анализа» (PDF) , Publ. Математика. Дебрецен , 10 (1–4): 10–13, doi :10.5486/PMD.1963.10.1-4.02.
  • Спенсер, Дж. (1995), «Асимптотическая упаковка с помощью ветвящегося процесса», Случайные структуры и алгоритмы , 7 (2): 167–172, doi :10.1002/rsa.3240070206.
  • Алон, Н.; Спенсер , Дж. (2008), Вероятностный метод (3-е изд.), Wiley-Interscience, Нью-Йорк, ISBN 978-0-470-17020-5.
  • Rödl, V. ; Thoma, L. (1996), "Асимптотическая упаковка и случайный жадный алгоритм", Случайные структуры и алгоритмы , 8 (3): 161–177, CiteSeerX  10.1.1.4.1394 , doi :10.1002/(SICI)1098-2418(199605)8:3<161::AID-RSA1>3.0.CO;2-W.
  • Спенсер, Дж.; Пиппенджер , Н. (1989), «Асимптотическое поведение хроматического индекса для гиперграфов», Журнал комбинаторной теории , Серия A, 51 (1): 24–42, doi : 10.1016/0097-3165(89)90074-5.
  • Алон, Нога ; Ким, Чон-Хан; Спенсер, Джоэл (1997), «Почти идеальные паросочетания в регулярных простых гиперграфах», Israel Journal of Mathematics , 100 (1): 171–187, CiteSeerX  10.1.1.483.6704 , doi :10.1007/BF02773639.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Packing_in_a_hypergraph&oldid=1193430724#The_Rödl_nibble"