Контейнерный метод

Метод контейнеров (гиперграфов) — мощный инструмент, который может помочь охарактеризовать типичную структуру и/или ответить на экстремальные вопросы о семействах дискретных объектов с заданным набором локальных ограничений. Такие вопросы естественным образом возникают в экстремальной теории графов , аддитивной комбинаторике , дискретной геометрии , теории кодирования и теории Рамсея ; они включают в себя некоторые из наиболее классических проблем в смежных областях.

Эти проблемы можно выразить в виде вопросов следующего вида: учитывая гиперграф $H$ на конечном множестве вершин $V$ с множеством ребер $E$ (т.е. набор подмножеств $V$ с некоторыми ограничениями на размер), что мы можем сказать о независимых множествах $H$ ( т.е. те подмножества $V$ , которые не содержат элементов $E$ )? Лемма о контейнере гиперграфа дает метод решения таких вопросов.

История

Одна из фундаментальных проблем экстремальной теории графов, относящаяся к работам Мантеля в 1907 году и Турана в 1940-х годах, требует охарактеризовать те графы, которые не содержат копию некоторого фиксированного запрещенного $H$ в качестве подграфа. В другой области одним из мотивирующих вопросов аддитивной комбинаторики является понимание того, насколько большим может быть набор целых чисел, не содержащий $k$ -членной арифметической прогрессии , с верхними границами этого размера, данными Ротом ( $k=3$ ) и Семереди (генерал $К$ ).

Метод контейнеров (в графах) впервые был предложен Клейтманом и Уинстоном в 1980 году, которые ограничили количество решеток. ^[1] и графики без 4-циклов. ^[2] Леммы контейнерного типа были независимо разработаны несколькими математиками в разных контекстах, в том числе Сапоженко, который первоначально использовал этот подход в 2002-2003 годах для перечисления независимых множеств в регулярных графах . ^[3] множества без сумм в абелевых группах, ^[4] и изучить множество других задач по перечислению ^[5]

Обобщение этих идей на лемму о контейнере гиперграфа было независимо разработано Сакстоном и Томасоном. ^[6] и Балог, Моррис и Самотидж ^[7] в 2015 году, вдохновленный множеством предыдущих работ.

Основная идея и неформальное заявление

Многие задачи комбинаторики можно переформулировать как вопросы о независимых множествах в графах и гиперграфах. Например, предположим, что мы хотим понять подмножества целых чисел от $1$ до $n$ , которые мы обозначаем через $[n]$ в которых отсутствует $k$ -членная арифметическая прогрессия. Эти множества являются в точности независимыми множествами в $k$ -равномерном гиперграфе. $H=(\{1,2,\ldots ,n\},E)$ , где $E$ — совокупность всех $k$ -членных арифметических прогрессий в $\{1,2,\ldots ,n\}$ .

В приведенных выше (и многих других) случаях обычно возникают два естественных класса задач, связанных с гиперграфом $H$ :

Каков размер максимального независимого множества в $H$ ? коллекция независимых множеств максимального размера в $H ?$ Как выглядит
Сколько независимых множеств $имеет H$ ? «типичное» независимое множество в $H ?$ Как выглядит

Эти проблемы связаны простым наблюдением. Позволять $\alpha (H)$ быть размером наибольшего независимого множества $H$ и предположим, что $H$ имеет $i(H)$ независимые множества. Затем,

2^{\alpha (H)}\leq i(H)\leq \sum _{r=0}^{\alpha (H)}{|V(H)| \choose r},

где нижняя оценка получается путем взятия всех подмножеств максимального независимого множества. Эти границы находятся относительно далеко друг от друга, если только $\alpha (H)$ очень велико, близко к числу вершин гиперграфа. Однако во многих гиперграфах, которые естественным образом возникают в комбинаторных задачах, у нас есть основания полагать, что нижняя граница ближе к истинному значению; таким образом, основная цель — улучшить верхние границы $i(H)$ .

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

Контейнеров не так уж и много.
Каждый контейнер ненамного больше самого большого независимого набора.
Каждый контейнер имеет несколько ребер.
Каждое независимое множество в гиперграфе полностью содержится в некотором контейнере.

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

Лемма о контейнере гиперграфа обеспечивает описанное выше разложение контейнера на две части. Он строит детерминированную функцию $f$ . Затем он предоставляет алгоритм, который извлекает из каждого независимого множества $I$ в гиперграфе $H$ относительно небольшой набор вершин. $S\subset I$ , называемый отпечатком пальца, обладающий свойством, $S\subset I\subset S\cup f(S)$ . Тогда контейнеры представляют собой коллекцию наборов $S\cup f(S)$ которые возникают в описанном выше процессе, а небольшой размер отпечатков пальцев обеспечивает хороший контроль количества таких наборов контейнеров.

Алгоритм графового контейнера

Сначала мы опишем метод показа строгих верхних границ количества независимых множеств в графе; эта экспозиция адаптирована на основе обзора Самотия. ^[8] о методе графового контейнера, первоначально использованном Клейтманом-Уинстоном и Сапоженко.

Обозначения

В приведенном ниже разделе мы используем следующие обозначения.

$G=(V,E)$ это график на $|V|=n$ вершины, где множество вершин снабжено (произвольным) упорядочением $\{v_{1},\ldots ,v_{n}\}$ .
Позволять $\ell (G)$ — совокупность независимых множеств $G$ размера $i(G):=|\ell (G)|$ . Позволять $i(G,r)$ — количество независимых наборов размера $r$ .
в максимальной степени Упорядочение подмножества вершин $A\subset V$ — это упорядочение вершин в $A$ по их степени в индуцированном подграфе $G[A]$ .

Алгоритм Клейтмана-Уинстона

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

Зафиксировать граф $G$ , независимое множество $I\in \ell (G)$ и положительное целое число $q\leq |I|$ .

Инициализировать : пусть $A=V(G),S=\emptyset$ .
Итерация для $s=1,2,\ldots ,q$ $s=1,2,\ldots,q$ :
- Постройте порядок максимальной степени $A,\,(v_{1},\ldots v_{|A|})$
- Найдите минимальный индекс $j_{s}$ такой, что $v_{j_{s}}\in I$ (т.е. вершина в $A$ наибольшей степени в индуцированном подграфе $G[A]$ )
- Позволять $S\leftarrow S\cup \{v_{j_{s}}\},\,A\leftarrow A\backslash (\{v_{1},\ldots ,v_{j_{s}}\}\cup N(v_{j_{s}}))$ , где $N(v)$ является окрестностью вершины $v$ .
Выведите вектор $(j_{1},\ldots ,j_{q})$ и набор вершин $A\cap I$ .

Анализ

По построению выходные данные приведенного выше алгоритма обладают свойством, которое $\{v_{j_{1}},\ldots ,v_{j_{q}}\}\subset I\subset \{v_{j_{1}},\ldots ,v_{j_{q}}\}\cup (A\cap I)$ , отметив, что $A\cap I$ является подмножеством вершин, которое полностью определяется $\{j_{1},\ldots ,j_{q}\}$ и не является иначе функцией $I$ . Чтобы подчеркнуть это, напишем $A=A(j_{1},\ldots ,j_{q})$ . Заметим также, что мы можем восстановить множество $S=\{v_{j_{1}},\ldots ,v_{j_{q}}\}=S(j_{1},\ldots j_{q})$ в приведенном выше алгоритме только из вектора $(j_{1},\ldots ,j_{q})$ .

Это говорит о том, что $S$ может быть хорошим выбором отпечатка пальца и $S(j_{1},\ldots j_{q})\cup A(j_{1},\ldots ,j_{q})$ хороший выбор контейнера . Точнее, мы можем оценить количество независимых наборов $G$ некоторого размера $r\geq q$ как сумма по выходным последовательностям $(j_{1},\ldots j_{q})$

i(G,r)=\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})],r-q)\leq \sum _{(j_{s})}{A(j_{1},\ldots j_{q}) \choose r-q}

,

где мы можем суммировать $r$ чтобы получить оценку общего количества независимых наборов графа:

i(G)=\sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})])\leq \sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})}2^{|A(j_{1},\ldots j_{q})|}

.

Пытаясь минимизировать эту верхнюю границу, мы хотим выбрать $q$ который уравновешивает/минимизирует эти два термина. Этот результат иллюстрирует ценность упорядочения вершин по максимальной степени (чтобы минимизировать $|A(j_{1},\ldots j_{q})|$ ).

Леммы

Приведенные выше неравенства и наблюдения можно сформулировать в более общей постановке, отдельно от явной суммы по векторам. $(j_{s})$ .

Лемма 1: Дан граф $G$ с $n$ и предположим, что целое число $q$ и реальные цифры $R,\beta \in [0,1]$ удовлетворить $R\geq e^{-\beta q}n$ . Предположим, что каждый индуцированный подграф хотя бы на $R$ вершины имеют плотность ребер не менее $\beta$ . Тогда для каждого целого числа $r\geq q$ ,

i(G,r)\leq {n \choose q}{R \choose r-q}.

Лемма 2: Пусть $G$ быть графиком на $n$ вершин и предположим, что целое число $q$ и реальные $R,D$ выбираются так, что $n\leq R+qD$ . Если все подмножества $U$ по крайней мере $R$ вершины имеют по крайней мере $D|U|/2$ края, то есть коллекция ${\mathcal {F}}$ подмножеств $q$ вершины («отпечатки пальцев») и детерминированная функция $f:{\mathcal {C}}\rightarrow {\mathcal {P}}(V(G)$ , так что для любого независимого множества $I\subset V(G)$ , есть $S\in {\mathcal {F}}$ такой, что $S\subset I\subset f(S)\cup S$ .

Лемма о контейнере гиперграфа

Неформально, лемма о контейнере гиперграфа говорит нам, что мы можем назначить небольшой отпечаток пальца. $S\subset I$ каждому независимому набору, так что все независимые наборы с одинаковым отпечатком принадлежат одному и тому же большему набору, $C=f(S)$ , связанный контейнер, размер которого ограничен количеством вершин гиперграфа. Кроме того, эти отпечатки малы (и, следовательно, контейнеров мало), и мы можем ограничить их размер по существу оптимальным способом, используя некоторые простые свойства гиперграфа.

Напомним следующие обозначения, связанные с $k$ однородный гиперграф ${\mathcal {H}}$ .

Определять $\Delta _{l}({\mathcal {H}}):=\max\{d_{H}(A)\mid A\subset V({\mathcal {H}}),|A|=l\}$ для положительных целых чисел $1\leq l\leq k$ , где $d_{\mathcal {H}}(A)=|\{e\in E({\mathcal {H}})\mid A\subset e\}|$ .
Позволять ${\mathcal {I}}({\mathcal {H}})$ быть совокупностью независимых наборов ${\mathcal {H}}$ . $I$ будет обозначать некоторое такое независимое множество.

Заявление

Мы излагаем версию этой леммы, найденную в работе Балога, Морриса, Самотиджа и Сакстона. ^[9]

Позволять ${\mathcal {H}}$ быть $k$ -однородный гиперграф и предположим, что для каждого $l\in \{1,2,\ldots ,k\}$ и некоторые $b,r\in \mathbb {N}$ , у нас это есть $\Delta _{l}(H)\leq \left({\frac {b}{|V(H)|}}\right)^{l-1}{\frac {|E(H)|}{r}}$ . Затем идет сбор ${\mathcal {C}}\subset {\mathcal {P}}(V(H))$ и функция $f:{\mathcal {P}}(V(H))\rightarrow {\mathcal {C}}$ такой, что

для каждого $I\in {\mathcal {I}}(H)$ существует $S\subset I$ с $|S|\leq (k-1)b$ и $I\subset f(S)$ .
$|C|\leq |V(H)|-\delta r$ для каждого $C\in {\mathcal {C}}$ и $\delta =2^{-k(k+1)}$ .

Примеры приложений

Обычные графики

Верхняя граница количества независимых множеств

Мы покажем, что существует абсолютная константа $C$ такая, что каждое $n$ -вершина $d$ -регулярный график $G$ удовлетворяет $i(G)\leq 2^{\left(1+C{\sqrt {\frac {\log d}{d}}}\right){\frac {n}{2}}}$ .

Мы можем ограничить количество независимых наборов каждого размера. $r$ используя тривиальную оценку $i(G,r)\leq {n \choose r}\leq {n \choose n/10}\leq 2^{0.48n}$ для $r\leq n/10$ .Для большего $r$ , брать $\beta >10/n,q=\lfloor 1/\beta \rfloor ,R={\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}.$ При этих параметрах $d$ -регулярный граф $G$ удовлетворяет условиям леммы 1 и, следовательно,

i(G,r)\leq {n \choose q}{R \choose r-q}\leq {n \choose q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq \left({\frac {en}{q}}\right)^{q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq (e\beta n)^{\lfloor 1/\beta \rfloor }{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}.

Подводя итог всему $0\leq r\leq n$ дает

i(G)\leq 2^{0.49n}+2^{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}+\lfloor 1/\beta \rfloor \log _{2}(e\beta n)}

,

который дает желаемый результат, когда мы подключаем $\beta ={\sqrt {d\log d}}/n.$

Наборы без сумм

Набор $A$ элементов абелевой группы называется свободной от сумм, если не существует $x,y,z\in A$ удовлетворяющий $x+y=z$ . Мы покажем, что существует не более $2^{(1/2+o(1))n}$ подмножества без сумм $[n]:=\{1,2,\ldots ,n\}$ .

Это будет следовать из наших приведенных выше оценок числа независимых множеств в регулярном графе. Чтобы убедиться в этом, нам нужно будет построить вспомогательный график. Сначала мы заметим, что с точностью до членов более низкого порядка мы можем ограничить наше внимание множествами без сумм с по крайней мере $n^{2/3}$ элементы меньше, чем $n/2$ (поскольку число подмножеств в дополнении к нему не более $(n/2)^{n^{2/3}}2^{n/2+1}$ ).

Учитывая некоторое подмножество $S\subset \{1,2,\ldots ,\lceil n/2\rceil -1\}$ , определим вспомогательный граф $G_{S}$ с набором вершин $[n]$ и набор кромок $\{\{x,y\}\mid x+s\equiv y{\pmod {n}}{\text{ for some }}s\in S\cup (-S)\}$ и заметим, что наш вспомогательный граф $2|S|$ регулярен, поскольку каждый элемент $S$ меньше $n/2$ . Тогда, если $S_{A}$ самые маленькие $n^{2/3}$ элементы подмножества $A\subset [n]$ , набор $A\backslash S_{A}$ является независимым множеством в графе $G_{S_{A}}$ . Тогда, согласно нашей предыдущей оценке, мы видим, что количество подмножеств без сумм $[n]$ самое большее

(n/2)^{n^{2/3}}2^{n/2+}+{n/2 \choose n^{2/3}}2^{(1+O(n^{-1/3}{\sqrt {\log n}})){\frac {n}{2}}}\leq 2^{(1/2+O(n^{-1/3}\log n))n}.

Графики без треугольников

Мы даем иллюстрацию использования леммы о контейнере гиперграфов для ответа на перечислительный вопрос, давая асимптотически точную верхнюю оценку числа графов без треугольников с $n$ вершины. ^[10]

Неофициальное заявление

Поскольку двудольные графы не содержат треугольников, количество графов без треугольников с $n$ вершин - это как минимум $2^{\lfloor n^{2}/4\rfloor }$ , полученный путем перечисления всех возможных подграфов сбалансированного полного двудольного графа $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$ .

Мы можем построить вспомогательный $3-$ однородный гиперграф $H$ с множеством вершин $V(H)=E(K_{n})$ и набор кромок $E(H)=\{\{e_{1},e_{2},e_{3}\}\subset E(K_{n})=V(H)\mid e_{1},e_{2},e_{3}{\text{ form a triangle}}\}$ . Этот гиперграф «кодирует» треугольники в том смысле, что семейство графов без треугольников на $n$ вершин — это в точности совокупность независимых множеств этого гиперграфа, ${\mathcal {I}}(H)$ .

Приведенный выше гиперграф имеет хорошее распределение степеней: каждое ребро $K_{n}$ , и, таким образом, вершина в $V(H)$ содержится ровно в $n-2$ треугольники и каждая пара элементов в $V(H)$ содержится не более чем в одном треугольнике. Следовательно, применяя лемму о контейнере гиперграфа (итеративно), мы можем показать, что существует семейство $n^{O(n^{3/2})}$ контейнеры, каждый из которых содержит несколько треугольников, содержащих каждый граф/независимый набор гиперграфа без треугольников.

Верхняя граница количества графов без треугольников

Сначала мы специализируем общую лемму о контейнере гиперграфов на 3-однородных гиперграфах следующим образом:

Лемма: Для каждого $c>0$ , существует $\delta >0$ такое, что имеет место следующее. Позволять $H$ быть 3-однородным гиперграфом средней степени $d\geq 1/\delta$ и предположим, что $\Delta _{1}(H)\leq cd,\Delta _{2}(H)\leq c{\sqrt {d}}$ . Тогда существует коллекция ${\mathcal {C}}\subset {\mathcal {P}}(V(H))$ максимум $|{\mathcal {C}}|\leq {|V(H)| \choose |V(H)|/{\sqrt {d}}}$ контейнеры такие, что

для каждого $I\in {\mathcal {I}}(H)$ , существует $I\subset C\in {\mathcal {C}}$
$|C|\leq (1-\delta )|V(H)|$ для всех $C\in {\mathcal {C}}$

Итеративное применение этой леммы даст следующую теорему (как доказано ниже):

Теорема: Для всех $\epsilon >0$ , существует $C>0$ такое, что имеет место следующее. Для каждого натурального числа $n$ существует набор ${\mathcal {G}}$ графов на $n$ вершинах с $|{\mathcal {G}}|\leq n^{Cn^{3/2}}$ такой, что

каждый $G\in {\mathcal {G}}$ имеет меньше, чем $\epsilon n^{3}$ треугольники,
каждый граф без треугольников на $n$ вершины содержатся в некоторых $G\in {\mathcal {G}}$ .

Доказательство: рассмотрим гиперграф $H$ определено выше. Как неофициально отмечалось ранее, гиперграф удовлетворяет условию $|V(H)|={n \choose 2},\Delta _{2}(H)=1,d(v)=n-2$ для каждого $v\in V(H)$ . Следовательно, мы можем применить приведенную выше лемму к $H$ с $c=1$ найти какую-нибудь коллекцию ${\mathcal {C}}$ из $n^{O(n^{3/2})}$ подмножества $E(K_{n})$ (т.е. графики на $n$ вершины) такие, что

любой граф без треугольников является подграфом некоторого $C\in {\mathcal {C}}$ ,
каждый $C\in {\mathcal {C}}$ имеет не более $(1-\delta ){n \choose 2}$ края.

Это не так строго, как результат, который мы хотим показать, поэтому мы будем итеративно применять лемму о контейнере. Предположим, у нас есть некоторый контейнер $C\in {\mathcal {C}}$ по крайней мере $\epsilon n^{3}$ треугольники. Мы можем применить лемму о контейнере к индуцированному подгиперграфу $H[C]$ . Средняя степень $H[C]$ по крайней мере $6\epsilon n$ , поскольку каждый треугольник в $C$ является преимуществом в $H[C]$ , и этот индуцированный подграф имеет не более ${n \choose 2}$ вершины. Таким образом, мы можем применить лемму с параметром $c=1/\epsilon$ , удалять $C$ из нашего набора контейнеров, заменив его на этот набор контейнеров, контейнеры, закрывающие ${\mathcal {I}}(H[C])$ .

Мы можем продолжать итерацию, пока не получим окончательную коллекцию контейнеров. ${\mathcal {C}}$ каждый из которых содержит менее $\epsilon n^{3}$ треугольники. Заметим, что эта коллекция не может быть слишком большой; все наши индуцированные подграфы имеют не более ${n \choose 2}$ вершины и средняя степень не менее $6\epsilon n$ , что означает, что каждая итерация дает не более $n^{O(n^{3/2})}$ новые контейнеры. Кроме того, размер контейнера уменьшается в разы. $1-\delta$ каждый раз, поэтому после ограниченного (в зависимости от $\epsilon$ ) количество итераций, итерационный процесс завершится.

См. также

Независимое множество (теория графов)
Теорема Семереди
Лемма Семереда о регулярности

Ссылки

^ Клейтман, Дэниел; Уинстон, Кеннет (1980). «Асимптотическое число решеток». Анналы дискретной математики . 6 : 243–249. дои : 10.1016/S0167-5060(08)70708-8 . ISBN 9780444860484 .
^ Клейтман, Дэниел; Уинстон, Кеннет (1982). «О числе графов без 4-циклов» . Дискретная математика . 31 (2): 167–172. дои : 10.1016/0012-365X(82)90204-7 .
^ Sapozhenko, Alexander (2003). "The Cameron-Erdos conjecture". Doklady Akademii Nauk . 393 : 749–752.
^ Сапоженко, Александр (2002). «Асимптотика числа множеств без сумм в абелевых группах». Доклады Академии наук . 383 : 454–458.
^ Сапоженко, Александр (2005), «Системы контейнеров и задачи перечисления» , Стохастические алгоритмы: основы и приложения , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 1–13, ISBN 978-3-540-29498-6 , получено 13 февраля 2022 г.
^ Сакстон, Дэвид; Томасон, Эндрю (2015). «Контейнеры гиперграфа». Математические изобретения . 201 (3): 925–992. arXiv : 1204.6595 . Бибкод : 2015InMat.201..925S . дои : 10.1007/s00222-014-0562-8 . S2CID 119253715 .
^ Балог, Йожеф; Моррис, Роберт; Самотий, Войцех (2015). «Независимые множества в гиперграфах» . Журнал Американского математического общества . 28 (3): 669–709. arXiv : 1204.6530 . дои : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650 .
^ Самотий, Войцех (2015). «Подсчет независимых множеств в графах». Европейский журнал комбинаторики . 48 : 5–18. arXiv : 1412.0940 . дои : 10.1016/j.ejc.2015.02.005 . S2CID 15850625 .
^ Балог, Йожеф; Моррис, Роберт; Самотий, Войцех (2015). «Независимые множества в гиперграфах» . Журнал Американского математического общества . 28 (3): 669–709. arXiv : 1204.6530 . дои : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650 .
^ Балог, Йожеф; Моррис, Роберт; Самотий, Войцех (2018). «Метод гиперграфов-контейнеров». Материалы Международного конгресса математиков: Рио-де-Жанейро . arXiv : 1801.04584 .

[1] Клейтман, Дэниел; Уинстон, Кеннет (1980). «Асимптотическое число решеток». Анналы дискретной математики . 6 : 243–249. дои : 10.1016/S0167-5060(08)70708-8 . ISBN 9780444860484 .

[2] Клейтман, Дэниел; Уинстон, Кеннет (1982). «О числе графов без 4-циклов» . Дискретная математика . 31 (2): 167–172. дои : 10.1016/0012-365X(82)90204-7 .

[3] Sapozhenko, Alexander (2003). "The Cameron-Erdos conjecture". Doklady Akademii Nauk . 393 : 749–752.

[4] Сапоженко, Александр (2002). «Асимптотика числа множеств без сумм в абелевых группах». Доклады Академии наук . 383 : 454–458.

[5] Сапоженко, Александр (2005), «Системы контейнеров и задачи перечисления» , Стохастические алгоритмы: основы и приложения , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 1–13, ISBN 978-3-540-29498-6 , получено 13 февраля 2022 г.

[6] Сакстон, Дэвид; Томасон, Эндрю (2015). «Контейнеры гиперграфа». Математические изобретения . 201 (3): 925–992. arXiv : 1204.6595 . Бибкод : 2015InMat.201..925S . дои : 10.1007/s00222-014-0562-8 . S2CID 119253715 .

[7] Балог, Йожеф; Моррис, Роберт; Самотий, Войцех (2015). «Независимые множества в гиперграфах» . Журнал Американского математического общества . 28 (3): 669–709. arXiv : 1204.6530 . дои : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650 .

[8] Самотий, Войцех (2015). «Подсчет независимых множеств в графах». Европейский журнал комбинаторики . 48 : 5–18. arXiv : 1412.0940 . дои : 10.1016/j.ejc.2015.02.005 . S2CID 15850625 .

[9] Балог, Йожеф; Моррис, Роберт; Самотий, Войцех (2015). «Независимые множества в гиперграфах» . Журнал Американского математического общества . 28 (3): 669–709. arXiv : 1204.6530 . дои : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650 .

[10] Балог, Йожеф; Моррис, Роберт; Самотий, Войцех (2018). «Метод гиперграфов-контейнеров». Материалы Международного конгресса математиков: Рио-де-Жанейро . arXiv : 1801.04584 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]