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

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

История

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

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

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

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

$H$ это ( $D_{0}$, $\epsilon$)-хороший гиперграф, если существует $D_{0}$ такой, что для всех $x,y\in V$ и $D\geq D_{0}$ и выполняются оба следующих условия.

$D(1-\epsilon )\leq {\text{deg}}(x)\leq D(1+\epsilon )$

${\text{codeg}}(x,y)\leq \epsilon D$

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

Теорема

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

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

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

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

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

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

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

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

Дерево с корнями, имеющее понятия родителя, потомка, корня, порядка рождения и сородича, будет называться расплодным деревом. Учитывая конечный выводок $T$ мы говорим о каждой вершине, что она выживает или умирает. Бездетная вершина сохраняется. Вершина умирает тогда и только тогда, когда в ней есть хотя бы один выводок, и все они выживают. Позволять $f(c)$ обозначают вероятность того, что Ева выживет в расплоде $T$ заданный вышеописанным процессом. Цель – показать $\lim _{c\rightarrow \infty }f(c)=0$ и тогда для любого фиксированного $c$, можно показать, что $\lim ^{*}f_{x,H}(c)=f(c)$. Эти два соотношения завершают наше рассуждение.

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

Чтобы доказать $\lim ^{*}f_{x,H}(c)=f(c)$Рассмотрим процедуру, которую мы называем «История», которая либо прерывает работу, либо создает выводковое дерево. История содержит множество $T$ вершин, первоначально $T=\{x\}$. $T$ будет иметь структуру расплода с $x$ корень. $y\in T$ либо обработанные, либо необработанные, $x$ изначально не обработан. Каждому $y\in T$ назначено время рождения $t_{y}$, мы инициализируем $t_{x}=c$. История – это брать необработанный $y\in T$ и обработайте его следующим образом. По ценности всего $t_{E}$ с $y\in E$ но без $x\in E$ который уже был обработан, если какой-либо $E$ имеет $t_{E}<t_{y}$ и $y,z\in E$ с $z\in T$ или некоторые $E,E'$ иметь $t_{E},t_{E'}<t_{y}$ с $y\in E,E'$ и $|E\cup E'|>1$, то история прерывается. В противном случае для каждого $E$ с $t_{E}<t_{y}$ добавить все $z\in E-\{y\}$ к $T$ как сородичи с родителем $y$ и общая дата рождения $t_{E}$. Сейчас $y$ считается обработанным. История останавливается, если не прерывается, когда все $y\in T$ обрабатываются. Если история не прерывается, то рутируйте $x$ выживает $T$ тогда и только тогда, когда $x$ выживает во время $c$. Для фиксированного расплода пусть $f(T,c)$ обозначают вероятность того, что в результате процесса ветвления образуется расплод $T$. Тогда вероятность того, что история не прервется, равна $f(T,c)$. В силу конечности ветвящегося процесса $\sum f(T,c)=1$, суммирование по всем расплодным деревьям $T$ и История не прерывается. $lim^{*}$ распределение его выводка приближается к распространению процесса ветвления. Таким образом $\lim ^{*}f_{x,H}(c)=f(c)$.

Клев Рёдля

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

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

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

Упаковка в более сильном состоянии

В 1997 году Нога Алон , Чон Хан Ким и Джоэл Спенсер также стали хорошими кандидатами на победу. $\gamma$ при более сильном условии костепени, согласно которому каждая отличная пара $v,v'\in V$ имеет не более одного общего ребра.

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

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

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

Впоследствии это улучшилось до $n/3-O({\frac {\log n}{\log \log n}})$ и ${\frac {n-4}{3}}$

См. также

• Процесс ветвления
• Независимый набор
• Раскраска графа
• Покрытие номер
• Упаковка комплекта
• Теорема Рамсея
• Установить проблему с обложкой
• Сферическая упаковка
• Система Штейнера

Ссылки

• Эрдеш, П .; Ханани, Х. (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 .
• Рёдль, В .; Тома, Л. (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 .