przypuszczenie Rysera

W teorii grafów przypuszczenie Rysera jest przypuszczeniem odnoszącym się do maksymalnego rozmiaru dopasowania i minimalnego rozmiaru poprzecznego w hipergrafach .

Przypuszczenie to pojawiło się po raz pierwszy w 1971 roku w pracy doktorskiej. praca magisterska JR Hendersona, której promotorem był Herbert John Ryser .

Czynności wstępne

Dopasowanie . w hipergrafie to zbiór hipergrafów, w których każdy wierzchołek występuje co najwyżej w jednym z nich Największy rozmiar dopasowania w hipergrafie H jest oznaczony przez ${\ Displaystyle \ nu (H)}$ .

Poprzeczne . (lub pokrycie wierzchołków ) w hipergrafie to zbiór wierzchołków taki, że każda hiperkrawędź zawiera co najmniej jeden z nich Najmniejszy rozmiar poprzecznej w hipergrafie H jest oznaczony przez ${\ Displaystyle \ tau (H)}$ .

Dla każdego , ponieważ każda okładka musi zawierać co $najmniej$

Jeśli H jest r -jednolita (każda hiperkrawędź ma dokładnie r wierzchołków), to ${\ Displaystyle \ tau (H) \ równoważnik r \ cdot \ nu (H)}$ , ponieważ związek krawędzi z dowolnego maksymalnego dopasowania to zbiór co najwyżej rv wierzchołków spełniających każdą krawędź.

przypuszczenie

Przypuszczenie Rysera jest takie, że jeśli H jest nie tylko r -jednolity, ale także r-cząstkowy (tj. jego wierzchołki można podzielić na r zbiorów, tak że każda krawędź zawiera dokładnie jeden element każdego zbioru), to:

${\ Displaystyle \ tau (H) \ równoważnik (r-1) \ cdot \ nu (H)}$

Tj. mnożnik w powyższej nierówności można zmniejszyć o 1.

Ekstremalne hipergrafy

Ekstremalny hipergraf $_ \nu (H)}$ Rysera . Istnienie takich hipergrafów świadczy o tym, że współczynnik r -1 jest najmniejszy z możliwych.

Przykładem hipergrafu ekstremalnego jest płaszczyzna rzutowa ścięta - płaszczyzna rzutowa rzędu r -1, w której usunięto jeden wierzchołek i wszystkie zawierające go linie. Wiadomo, że istnieje zawsze, gdy r -1 jest potęgą liczby całkowitej pierwszej.

Istnieją inne rodziny takich ekstremalnych hipergrafów.

Przypadki specjalne

W przypadku r = 2 hipergraf staje się wykresem dwudzielnym , a przypuszczenie staje się . ${\ Displaystyle \ tau (H) \ równoważnik \ nu (H)}$ . Wiadomo, że jest to prawdą z twierdzenia Kőniga .

W przypadku r = 3 przypuszczenie zostało udowodnione przez Rona Aharoniego . Dowód wykorzystuje twierdzenie Aharoniego-Haxella do dopasowywania w hipergrafach.

W przypadkach r =4 i r =5 Penny Haxell i Scott udowodnili następującą słabszą wersję : istnieje pewne ε > 0 takie, że

${\ Displaystyle \ tau (H) \ równoważnik (r- \ varepsilon) \ cdot \ nu (H)}$ .

Ponadto w przypadkach r = 4 i r = 5 przypuszczenie Rysera zostało udowodnione przez Tuzę (1978) w szczególnym przypadku , tj.: ν $\ Displaystyle \ nu (H) = 1}$

${\ Displaystyle \ nu (H) = 1 \ implikuje \ tau (H) \ równoważnik r-1}$ .

Warianty ułamkowe

Dopasowanie ułamkowe w hipergrafie to przypisanie wagi do każdej hipergrafu w taki sposób, że suma wag w pobliżu każdego wierzchołka wynosi co najwyżej jeden. Największy rozmiar dopasowania ułamkowego w hipergrafie H jest oznaczony przez . ${\ Displaystyle \ nu ^ {*} (H)}$ .

Ułamkowa poprzeczna w hipergrafie to przypisanie wagi do każdego wierzchołka w taki sposób, że suma wag w każdej hipergrafie wynosi co najmniej jeden. Najmniejszy rozmiar ułamkowej poprzecznej w hipergrafie H jest oznaczony przez . ${\ Displaystyle \ tau ^ {*} (H)}$ . Dualność programowania liniowego oznacza, że ${\ Displaystyle \ nu ^ {*} (H) = \ tau ^ {*} (H)}$ .

Furedi udowodnił następującą ułamkową wersję hipotezy Rysera: Jeśli H jest r -częściowe i r -regularne (każdy wierzchołek pojawia się dokładnie w r hiperkrawędziach), to

${\ Displaystyle \ tau ^ {*} (H) \ równoważnik (r-1) \ cdot \ nu (H)}$ .

Lovasz to pokazał

${\ Displaystyle \ tau (H) \ równoważnik {\ Frac {r} {2}} \ cdot \ nu ^ {*} (H)}$ .