WikiDer > Гипотеза Райзера - Википедия

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

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

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

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

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

Для каждого ЧАС, ${ Displaystyle ню (Ч) Leq тау (Н)}$, так как каждое покрытие должно содержать хотя бы одну точку с каждого края в любом совпадении.

Если H равно р-однородный (каждое гиперребро имеет ровно р вершины), то ${ Displaystyle тау (ЧАС) Leq г CDOT Nu (Н)}$, поскольку объединение ребер из любого максимального паросочетания представляет собой набор не более чем rv вершины, которые пересекают каждое ребро.

Гипотеза

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

${ Displaystyle тау (ЧАС) Leq (г-1) CDOT Nu (Н)}$

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

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

An экстремальный гиперграф к гипотезе Райзера является гиперграфом, в котором гипотеза верна с равенством, т. е. ${ Displaystyle тау (ЧАС) = (г-1) CDOT Nu (Н)}$. Существование таких гиперграфов показывает, что множитель р-1 - это наименьшее возможное.

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

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

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

В случае р= 2, гиперграф становится двудольный граф, и гипотеза принимает вид ${ Displaystyle тау (Н) Leq Nu (Н)}$. Это правда, как известно Теорема Кёнига.

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

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

${ Displaystyle тау (H) Leq (r- varepsilon) CDOT Nu (H)}$.

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

${ Displaystyle Nu (H) = 1 подразумевает tau (H) Leq r-1}$.

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

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

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

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

${ Displaystyle тау ^ {*} (ЧАС) Leq (г-1) CDOT Nu (Н)}$.

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

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

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