Гипотеза Райзера - Rysers conjecture - Wikipedia

В теория графов, Гипотеза Райзера гипотеза, связывающая максимальный размер согласования и минимальный поперечный размер в гиперграфы.

Эта гипотеза впервые появилась в 1971 г. в докторской диссертации. диссертацию Дж. Р. Хендерсона, научным руководителем которого был Герберт Джон Райзер.^[1]

Предварительные мероприятия

А соответствие в гиперграфе такое множество гиперребер, что каждая вершина входит не более чем в одно из них. Наибольший размер соответствия в гиперграфе ЧАС обозначается ${\displaystyle \nu (H)}$.

А поперечный (или же крышка вершины) в гиперграфе - такой набор вершин, что каждое гиперребро содержит хотя бы одну из них. Наименьший размер трансверсали в гиперграфе ЧАС обозначается ${\displaystyle \tau (H)}$.

Для каждого ЧАС, ${\displaystyle \nu (H)\leq \tau (H)}$, так как каждое покрытие должно содержать хотя бы одну точку с каждого края в любом совпадении.

Если H равно р-однородный (каждое гиперребро имеет ровно р вершины), то ${\displaystyle \tau (H)\leq r\cdot \nu (H)}$, поскольку объединение ребер из любого максимального паросочетания представляет собой набор не более чем rv вершины, которые пересекают каждое ребро.

Гипотеза

Гипотеза Райзера состоит в том, что если H не только р-униформа, но также r-partite (т.е. его вершины можно разбить на р наборы так, чтобы каждое ребро содержало ровно один элемент каждого набора), то:

${\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)}$

То есть мультипликативный множитель в приведенном выше неравенстве можно уменьшить на 1.^[2]

Экстремальные гиперграфы

An экстремальный гиперграф к гипотезе Райзера является гиперграфом, в котором гипотеза верна с равенством, т. е. ${\displaystyle \tau (H)=(r-1)\cdot \nu (H)}$. Существование таких гиперграфов показывает, что множитель р-1 - это наименьшее возможное.

Примером экстремального гиперграфа является усеченная проективная плоскость - в проективная плоскость порядка р-1, в котором одна вершина и все строки, содержащие ее, удаляются.^[3] Известно, что он существует всякий раз, когда р-1 - степень простого целого числа.

Существуют и другие семейства таких экстремальных гиперграфов.^[4]

Особые случаи

В случае р= 2, гиперграф становится двудольный граф, и гипотеза принимает вид ${\displaystyle \tau (H)\leq \nu (H)}$. Это правда, как известно Теорема Кёнига.

В случае р= 3, гипотеза доказана Рон Ахарони.^[5] Доказательство использует Теорема Ахарони-Хакселла для сопоставления в гиперграфах.

В случаях р= 4 и р= 5, следующая более слабая версия доказана Пенни Хакселл и Скотт:^[6] существует такое ε> 0, что

${\displaystyle \tau (H)\leq (r-\varepsilon )\cdot \nu (H)}$.

Более того, в случаях р= 4 и р= 5, гипотеза Райзера была доказана Тузой (1978) в частном случае ${\displaystyle \nu (H)=1}$, то есть:

${\displaystyle \nu (H)=1\implies \tau (H)\leq r-1}$.

Дробные варианты

А дробное соответствие в гиперграфе - это присвоение веса каждому гиперребру так, что сумма весов около каждой вершины не превосходит единицы. Наибольший размер дробного соответствия в гиперграфе ЧАС обозначается ${\displaystyle \nu ^{*}(H)}$.

А дробно-поперечный в гиперграфе - это присвоение веса каждой вершине так, чтобы сумма весов на каждом гиперребре была не меньше единицы. Наименьший размер дробной трансверсали в гиперграфе ЧАС обозначается ${\displaystyle \tau ^{*}(H)}$. Двойственность линейного программирования подразумевает, что ${\displaystyle \nu ^{*}(H)=\tau ^{*}(H)}$.

Фуреди доказал следующую дробную версию гипотезы Райзера: если ЧАС является р-частный и р-регулярно (каждая вершина появляется ровно р гиперребра), то^[7]

${\displaystyle \tau ^{*}(H)\leq (r-1)\cdot \nu (H)}$.

Ловаш показал, что^[8]

${\displaystyle \tau (H)\leq {\frac {r}{2}}\cdot \nu ^{*}(H)}$.

Рекомендации

1. Линь, Бо (2014). «Введение в гипотезу Райзера» (PDF).
2. "Гипотеза Райзера | Сад открытых проблем". www.openproblemgarden.org. Получено 2020-07-14.
3. Туза (1983). «Гипотеза Райзера о трансверсалей r-долевых гиперграфов». Ars Combinatorica.
4. Абу-Хазне, Ахмад; Барат, Янош; Покровский, Алексей; Сабо, Тибор (12.07.2018). «Семейство экстремальных гиперграфов для гипотезы Райзера». arXiv:1605.06361 [math.CO ].
5. Ахарони, Рон (01.01.2001). «Гипотеза Райзера для трехчастных 3-графов». Комбинаторика. 21 (1): 1–4. Дои:10.1007 / s004930170001. ISSN  0209-9683. S2CID  13307018.
6. Haxell, P.E .; Скотт, А. Д. (21 января 2012 г.). "По предположению Райзера". Электронный журнал комбинаторики. 19 (1). Дои:10.37236/1175. ISSN  1077-8926.
7. Фюреди, Золтан (1 июня 1981 г.). «Максимальные степени и дробные сопоставления в однородных гиперграфах». Комбинаторика. 1 (2): 155–162. Дои:10.1007 / bf02579271. ISSN  0209-9683. S2CID  10530732.
8. Ловас, Л. (1974), "Теоремы о минимаксе для гиперграфов", Семинар по гиперграфу, Конспект лекций по математике, Берлин, Гейдельберг: Springer Berlin Heidelberg, 411, стр. 111–126, Дои:10.1007 / bfb0066186, ISBN  978-3-540-06846-4