Гипотеза Райзера

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

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

Предварительные

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

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

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

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

Догадка

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

τ ( ЧАС ) ≤ ( г − 1 ) ⋅ ν ( ЧАС ) {\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)}

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

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

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

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

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

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

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

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

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

τ ( H ) ≤ ( r − ε ) ⋅ ν ( H ) {\displaystyle \tau (H)\leq (r-\varepsilon )\cdot \nu (H)} .

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

ν ( H ) = 1 ⟹ τ ( H ) ≤ r − 1 {\displaystyle \nu (H)=1\implies \tau (H)\leq r-1} .

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

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

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

Фуреди доказал следующую дробную версию гипотезы Райзера: если H является r -дольным и r -регулярным (каждая вершина появляется ровно в r гиперребрах), то [7]

τ ∗ ( H ) ≤ ( r − 1 ) ⋅ ν ( H ) {\displaystyle \tau ^{*}(H)\leq (r-1)\cdot \nu (H)} .

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

τ ( H ) ≤ r 2 ⋅ ν ∗ ( H ) {\displaystyle \tau (H)\leq {\frac {r}{2}}\cdot \nu ^{*}(H)} .

Ссылки

  1. ^ Линь, Бо (2014). «Введение в гипотезу Райзера» (PDF) .
  2. ^ "Гипотеза Райзера | Открытый проблемный сад". www.openproblemgarden.org . Получено 14 июля 2020 г.
  3. ^ Tuza (1983). «Гипотеза Райзера о трансверсалях r-дольных гиперграфов». Ars Combinatorica .
  4. ^ Абу-Хазне, Ахмад; Барат, Янош; Покровский, Алексей; Сабо, Тибор (12 июля 2018 г.). «Семейство экстремальных гиперграфов для гипотезы Райзера». arXiv : 1605.06361 [math.CO].
  5. ^ Ахарони, Рон (1 января 2001 г.). «Гипотеза Райзера для трехдольных трехграфов». Комбинаторика . 21 (1): 1–4 . doi : 10.1007/s004930170001. ISSN  0209-9683. S2CID  13307018.
  6. ^ Хакселл, П.Е.; Скотт, А.Д. (2012-01-21). «О гипотезе Райзера». Электронный журнал комбинаторики . 19 (1). doi : 10.37236/1175 . ISSN  1077-8926.
  7. ^ Фюреди, Золтан (1981-06-01). «Максимальная степень и дробные паросочетания в однородных гиперграфах». Combinatorica . 1 (2): 155– 162. CiteSeerX 10.1.1.115.2493 . doi :10.1007/bf02579271. ISSN  0209-9683. S2CID  10530732. 
  8. ^ Ловас, Л. (1974), «Теоремы минимакса для гиперграфов», Hypergraph Seminar , Lecture Notes in Mathematics, т. 411, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр.  111–126 , doi :10.1007/bfb0066186, ISBN 978-3-540-06846-4
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ryser%27s_conjecture&oldid=1195077516"