Twierdzenia typu Halla dla hipergrafów

W matematycznej dziedzinie teorii grafów twierdzenia typu Halla dla hipergrafów to kilka uogólnień twierdzenia Halla o małżeństwie od grafów do hipergrafów . Takie twierdzenia udowodnili Ofra Kessler, Ron Aharoni , Penny Haxell , Roy Meshulam i inni.

Czynności wstępne

Twierdzenie Halla o małżeństwie dostarcza warunku gwarantującego, że $graf$ dwudzielny $(X + Y, E)$ dopuszcza doskonałe dopasowanie , lub - bardziej ogólnie - dopasowanie , które nasyca wszystkie wierzchołki Y. Warunek obejmuje liczbę sąsiadów podzbiorów Y $.$ Uogólnienie twierdzenia Halla na hipergrafy wymaga uogólnienia pojęć dwudzielności, doskonałego dopasowania i sąsiadów.

1. Dwustronność : Pojęcie dwustronności można rozszerzyć na hipergrafy na wiele sposobów (patrz hipergraf dwudzielny ). Tutaj definiujemy hipergraf jako dwudzielny, jeśli jest dokładnie 2- kolorowy , tj. jego wierzchołki mogą być 2-kolorowe, tak że każda hipergraf zawiera dokładnie jeden żółty wierzchołek. Innymi słowy, $V$ można podzielić na dwa zbiory $X$ i $Y$ , tak że każda hiperkrawędź zawiera dokładnie jeden wierzchołek $Y$ . Wykres dwudzielny jest szczególnym przypadkiem, w którym każda krawędź zawiera dokładnie jeden wierzchołek $Y$ i dokładnie jeden wierzchołek $X$ ; w hipergrafie dwudzielnym każdy hipergraf zawiera dokładnie jeden wierzchołek $Y$ , ale może zawierać zero lub więcej wierzchołków $X$ . Na przykład hipergraf $(V, E)$ z $V = {1,2,3,4,5,6}$ i $E = { {1,2,3}, {1,2,4}, {1,3 ,4}, {5,2}, {5,3,4,6} }$ jest dwudzielne z $Y = {1,5}$ i $X = {2,3,4,6}.$

2. Dopasowanie idealne : Dopasowanie w hipergrafie $H = (V, E)$ jest podzbiorem $F$ z $E$ , takim, że każde dwie hiperkrawędzie $F$ są rozłączne. Jeśli $H$ jest dwudzielny z częściami $X$ i $Y$ , to rozmiar każdego dopasowania wynosi oczywiście co najwyżej $| Y |$ . Dopasowanie nazywa się $Y$ -perfect (lub $Y$ -saturating ), jeśli jego rozmiar jest dokładny $| Y |$ . Innymi słowy: każdy wierzchołek $Y$ pojawia się dokładnie w jednej hiperkrawędzi $M$ . Ta definicja sprowadza się do standardowej definicji $Y$ w grafie dwudzielnym.

3. Sąsiedzi : biorąc pod uwagę dwudzielny hipergraf $H = (X + Y, E)$ i podzbiór $Y 0$ z $Y$ , sąsiedzi $Y 0$ są podzbiorami $X$ , które dzielą hiperkrawędzie z wierzchołkami $Y 0$ . Formalnie:

{\ Displaystyle N_ {H} (Y_ {0}): = \ {X_ {0} \ subseteq X ~ ~ | ~ ~ \ istnieje y_ {0} \ w Y_ {0}: ~ \ {y_ {0} \ }\cup X_{0}\w E\}.}

Na przykład w hipergrafie z punktu 1 mamy: $N H ({1}) = { {2,3}, {2,4}, {3,4} }$ i $N H ({5}) = { {2}, {3,4,6} }$ i $N H ({1,5}) = { {2,3}, {2,4}, {3,4}, {2}, {3,4 ,6} }. Zauważ, że w grafie dwudzielnym każdy$ sąsiad jest singletonem - sąsiadami są po prostu wierzchołki $X$ , które sąsiadują z jednym lub więcej wierzchołkami $Y. 0$ W hipergrafie dwudzielnym każdy sąsiad jest zbiorem - sąsiedzi to podzbiory $X$ , które „przylegają” do jednego lub więcej wierzchołków $Y. 0$ _

Ponieważ $zdefiniować 0 NH (Y) zawiera$ $tylko 0 NH (Y)$ podzbiory $X , można$ hipergraf, w którym zbiorem wierzchołków jest $X$ , a zbiorem krawędzi jest . Nazywamy to hipergrafem sąsiedztwa $Y 0$ i oznaczamy:

{\ Displaystyle H_ {H} (Y_ {0}): = (X, N_ {H} (Y_ {0})).}

Zauważmy, że jeśli $H$ jest prostym grafem dwudzielnym, hipergraf sąsiedztwa każdego $Y 0$ zawiera tylko sąsiadów $Y 0$ w $X$ , z których każdy ma własną pętlę.

Niewystarczalność stanu Halla

Warunek Halla wymaga, aby dla każdego podzbioru $Y 0$ z $Y$ zbiór sąsiadów $Y 0$ był wystarczająco duży. W przypadku hipergrafów warunek ten jest niewystarczający. Rozważmy na przykład trójdzielny hipergraf z krawędziami:

{ {1, a, A}, {2, a, B} }

Niech $Y = {1,2}.$ Każdy wierzchołek w $Y$ ma sąsiada, a sam $Y$ ma dwóch sąsiadów: $N H (Y) = { {a,A}, {a,B} }.$ Ale nie ma idealnego dopasowania $Y$ , ponieważ obie krawędzie zachodzą na siebie. Można spróbować to naprawić, wymagając, aby $0 N H (Y)$ zawierało co najmniej $| Y 0 |$ rozłączne krawędzie, a nie tylko $| Y 0 |$ krawędzie. Innymi słowy $: H.H 0 (Y)$ powinien zawierać dopasowanie rozmiaru co najmniej $| Y 0 |$ . Największy rozmiar dopasowania w hipergrafie $H$ nazywany jest jego liczbą dopasowania i oznaczany przez $ν (H)$ (stąd $H$ dopuszcza dopasowanie $Y$ -doskonałe wtedy i tylko wtedy, gdy $ν (H) = | Y |$ ). Jednak ta poprawka jest niewystarczająca, jak pokazano na poniższym trójdzielnym hipergrafie:

{ {1, a, A}, {1, b, B}, {2, a, B}, {2, b, A} }

Niech $Y = {1,2}.$ Ponownie każdy wierzchołek w $Y$ ma sąsiada, a sam $Y$ ma czterech sąsiadów: $N H (Y) = { {a, A}, {a, B}, {b, A}, {b, B} }.$ Ponadto $ν (H H (Y)) = 2$ , ponieważ $H H (Y)$ dopuszcza dopasowanie rozmiaru 2, np. ${ {a,A}, {b,B} } lub { {a,B}, {b, A} }.$ Jednak H nie przyznaje $Y$ -idealne dopasowanie, ponieważ każda hiperkrawędź zawierająca 1 zachodzi na każdą hiperkrawędź zawierającą 2.

Dlatego, aby zagwarantować idealne dopasowanie, potrzebny jest silniejszy warunek. Sugerowano różne takie warunki.

Warunki Aharoniego: największe dopasowanie

Niech $H = (X + Y, E)$ będzie hipergrafem dwudzielnym (zgodnie z definicją w punkcie 1 powyżej), w którym rozmiar każdej hiperkrawędzi wynosi dokładnie $r$ , dla pewnej liczby całkowitej $r > 1$ . Załóżmy, że dla każdego podzbioru $Y 0$ z $Y$ zachodzi następująca nierówność:

{\ Displaystyle \ nu (N_ {H} (Y_ {0})) \ geq (r-1) \ cdot (|Y_{0}|-1)+1}

Słownie: hipergraf sąsiedztwa $Y 0$ dopuszcza dopasowanie większe niż $(r - 1) (| Y 0 | - 1)$ . Następnie $H$ dopuszcza idealne dopasowanie $Y$ (zgodnie z definicją w punkcie 2 powyżej).

Zostało to po raz pierwszy przypuszczone przez Aharoni. Udowodniono to wraz z Ofrą Kessler dla hipergrafów dwudzielnych, w których $| Y | \leq 4$ i dla $| Y | = 5$ . Zostało to później udowodnione dla wszystkich $r$ -jednolitych hipergrafów.

W prostych wykresach

Dla prostego wykresu dwudzielnego $r = 2$ , a warunek Aharoniego przyjmuje postać:

{\ Displaystyle \ nu (H_ {H} (Y_ {0})) \ geq | Y_ {0} |.}

Co więcej, hipergraf sąsiedztwa (zgodnie z definicją w punkcie 3. powyżej) zawiera tylko singletony - singleton dla każdego sąsiada $Y 0$ . Ponieważ singletony nie przecinają się, cały zestaw singletonów jest dopasowany. Stąd $0 ν (H H (Y)) = | 0 N H (Y) | =$ liczba sąsiadów $Y 0$ . Zatem warunek Aharoniego staje się dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle | N_ {H} (Y_ {0}) | \ geq | Y_ {0} |.}

To jest dokładnie warunek małżeństwa Halla.

Szczelność

Poniższy przykład pokazuje, że współczynnika $(r - 1)$ nie można poprawić. Wybierz jakąś liczbę całkowitą $m > 1$ . Niech $H = (X + Y, E)$ będzie następującym $r-$ jednolitym hipergrafem dwudzielnym:

$Y = {1, ..., m};$
E jest sumą E ₁ , … , E _m (gdzie E _i jest zbiorem hiperkrawędzi zawierających wierzchołek i ) oraz:
- Dla każdego $i$ w ${1, \dots , m - 1},$ $E i$ zawiera $r - 1$ rozłącznych hiperkrawędzi w rozmiarze $r$ :

${\ Displaystyle \ {i, x_ {i, 1,1}, \ ldots, x_ {i, 1, r-1} \}, \ ldots, \ {i, x_ {i, r-1,1}, \ldots ,x_{i,r-1,r-1}\}.}$

- $E m$ zawiera $m - 1$ hiperkrawędzi o rozmiarze $r$ :

${\ Displaystyle \ {m, x_ {1,1,1}, \ ldots, x_ {1, r-1, r-1}, \}, \ ldots, \ {m, x_ {m-1,1, 1},\ldokropki,x_{m-1,r-1,1}\}}$

Zauważ, że krawędź $i$ w $E m$ styka się ze wszystkimi krawędziami w $E i$ .

To $H$ nie dopuszcza idealnego dopasowania $Y$ , ponieważ każda hiperkrawędź zawierająca $m$ przecina wszystkie hiperkrawędzie w $Ei dla$ pewnego $i < m$ .

Jednak każdy podzbiór $Y 0$ z $Y$ spełnia następującą nierówność

{\ Displaystyle \ nu (H_ {H} (Y_ {0})) \ geq (r-1) \ cdot (| T_{0}|-1)}

ponieważ $0 H H ( Y \ { m })$ zawiera co najmniej $(r - 1) \cdot (| Y 0 | - 1)$ hiperkrawędzi i wszystkie są rozłączne.

Dopasowania ułamkowe

Największy rozmiar dopasowania ułamkowego w $H$ jest oznaczony przez $ν *(H)$ . Oczywiście $ν *(H) \geq ν (H)$ . Załóżmy, że dla każdego podzbioru $Y 0$ z $Y$ obowiązuje następująca słabsza nierówność:

{\ Displaystyle \ nu ^ {*} (H_ {H} (Y_ {0})) \ geq (r -1)\cdot (|Y_{0}|-1)+1}

Przypuszczano, że również w tym przypadku $H$ dopuszcza idealne dopasowanie $Y.$ To silniejsze przypuszczenie zostało udowodnione dla hipergrafów dwudzielnych, w których $| Y | = 2$ .

Później udowodniono, że jeśli powyższy warunek jest spełniony, to $H$ dopuszcza ułamkowe dopasowanie $Y$ -doskonałe , tj. $ν *(H) = | Y |$ . Jest to słabsze niż posiadanie $Y$ , które jest równoważne z $ν (H) = | Y |$ .

Warunek Haxella: najmniejszy poprzeczny

Transwersalny (zwany także wierzchołkiem-pokryciem lub zestawem uderzającym ) $w$ hipergrafie $H = (V, E)$ jest podzbiorem $U$ z $V$ takim, że każda hiperkrawędź w $E$ zawiera co najmniej jeden wierzchołek U . Najmniejszy rozmiar poprzecznej w $H$ jest oznaczony przez $τ (H)$ .

Niech $H = (X + Y, E)$ będzie hipergrafem dwudzielnym , w którym rozmiar każdej hiperkrawędzi wynosi co najwyżej $r$ , dla pewnej liczby całkowitej $r > 1$ . Załóżmy, że dla każdego podzbioru $Y 0$ z $Y$ zachodzi następująca nierówność:

{\ Displaystyle \ tau (H_ {H} (Y_ {0})) \ geq (2r-3) \ cdot (|Y_{0}|-1)+1}

Innymi słowy: hipergraf sąsiedztwa $Y 0$ nie ma poprzecznej wielkości $0 (2 r - 3) (Y - 1)$ lub mniejszej.

Następnie $H$ dopuszcza idealne dopasowanie $Y$ (jak zdefiniowano w punkcie 2. powyżej).

W prostych wykresach

Dla prostego wykresu dwudzielnego $r = 2$ więc $2 r - 3 = 1$ , a warunek Haxella przyjmuje postać:

{\ Displaystyle \ tau (H_ {H} (Y_ {0})) \ geq | Y_ {0} |.}

Co więcej, hipergraf sąsiedztwa (zgodnie z definicją w punkcie 3. powyżej) zawiera tylko singletony - singleton dla każdego sąsiada $Y 0$ . W hipergrafie singletonów poprzeczny musi zawierać wszystkie wierzchołki. Stąd $0 τ (H H (Y)) = | 0 N H (Y) | =$ liczba sąsiadów $Y 0$ . Zatem warunek Haxella staje się dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle | N_ {H} (Y_ {0}) | \ geq | Y_ {0} |.}

To jest dokładnie warunek małżeństwa Halla. Zatem twierdzenie Haxella implikuje twierdzenie Halla o małżeństwie dla prostych grafów dwudzielnych.

Szczelność

Poniższy przykład pokazuje, że współczynnika $(2 r - 3)$ nie można poprawić. Niech $H = (X + Y, E)$ będzie $r-$ jednolitym hipergrafem dwudzielnym z:

${\ Displaystyle Y = \ {0,1 \}}$
${\ Displaystyle X = \ {x_ {ij}: 1 \ równoważnik ja, j \ równoważnik r-1 \}}$

[więc $| X | = (r - 1) 2$ ].

${\ Displaystyle E = E_ {0} \ kubek E_ {1},}$

Gdzie:

- ${\ Displaystyle E_ {0} = \ {\ {0, x_ {i1}, \ ldots, x_ {i (r-1)} \} | 1 \ równoważnik ja \ równoważnik r- 1\}}$

[więc $E 0$ zawiera $r - 1$ hiperkrawędzie].

- ${\ Displaystyle E_ {1} = \ {\ {1, x_ {1j [1]}, \ ldots, x_ {(r-1) j [r-1]} \ }|1\równoważnik j[k]\równoważnik r-1}$

dla ${\ Displaystyle 1 \ równoważnik k \ równoważnik r-1 \}}$

[więc $E 1$ zawiera $(r - 1) r -1$ hiperkrawędzie].

To $H$ nie dopuszcza idealnego dopasowania $Y$ , ponieważ każda hiperkrawędź zawierająca 0 przecina każdą hiperkrawędź zawierającą 1.

Jednak każdy podzbiór $Y 0$ z $Y$ spełnia następującą nierówność:

{\ Displaystyle \ tau (H_ {H} (Y_ {0})) \ geq (2r-3) \ cdot ( |Y_{0}|-1)}

Jest tylko nieznacznie słabszy (o 1) niż wymaga tego twierdzenie Haxella. Aby to zweryfikować, wystarczy sprawdzić podzbiór $0 Y = Y$ , ponieważ jest to jedyny podzbiór, dla którego prawa strona jest większa od 0. Hipergraf sąsiedztwa $Y$ to $(X, E 00 \cup E 11)$ gdzie :

{\ Displaystyle E_ {00} = \ {\ {x_ {i1}, \ ldots, x_ {i (r-1)} \} | 1 \ równoważnik ja \ równoważnik r-1 \ }}

{\ Displaystyle E_ {11} = \ {\ {x_ {1j [1]}, \ ldots, x_ {(r-1) j [r-1]} \} | 1 \ równoważnik j [k] \ równoważnik r-1}

dla

{\ Displaystyle 1 \ równoważnik k \ równoważnik r-1 \}}

Wierzchołki $X można zwizualizować$ jako ułożone na siatce $(r - 1) \times (r - 1)$ . Hiperkrawędzie $E 00$ to rzędy $r - 1$ . Hiperkrawędzie $E 11$ to $(r - 1) r -1$ selekcje pojedynczego elementu w każdym rzędzie iw każdej kolumnie. Aby pokryć hiperkrawędzie $E 10$ potrzebujemy $r - 1$ wierzchołki - jeden wierzchołek w każdym rzędzie. Ponieważ wszystkie kolumny są symetryczne w konstrukcji, możemy założyć, że bierzemy wszystkie wierzchołki w kolumnie 1 (tj. $v i 1$ dla każdego $i$ w ${1, \dots, r - 1})$ . Teraz, ponieważ $E 11$ zawiera wszystkie kolumny, potrzebujemy co najmniej $r - 2$ dodatkowe wierzchołki – po jednym wierzchołku dla każdej kolumny ${2, \dots, r}.$ W sumie każda poprzeczna wymaga co najmniej $2 r - 3$ wierzchołków.

Algorytmy

Dowód Haxella nie jest konstruktywny. Jednak Chidambaram Annamalai udowodnił, że idealne dopasowanie można skutecznie znaleźć w nieco silniejszych warunkach.

Dla każdego ustalonego wyboru $r \geq 2$ i $ε > 0$ istnieje algorytm, który znajduje $Y$ -doskonałe dopasowanie w każdym $r$ -jednolitym dwudzielnym hipergrafie spełniającym, dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle \ tau (H_ {H} (Y_ {0})) \ geq (2r-3 +\epsilon )\cdot (|Y_{0}|-1)+1}

W rzeczywistości w każdym hipergrafie $r$ -jednostajnym algorytm znajduje albo idealne dopasowanie $Y$ , albo podzbiór $Y 0$ naruszający powyższą nierówność.

Algorytm działa w czasie wielomianowym w rozmiarze $H$ , ale wykładniczym w $r$ i $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 1 ⁄ ε$ .

Otwarte jest pytanie, czy istnieje algorytm z wielomianem w czasie wykonywania w $r$ lub $1 ⁄ ε$ (lub w obu).

Podobne algorytmy zastosowano do rozwiązywania problemów sprawiedliwego przydziału przedmiotów , w szczególności problemu Świętego Mikołaja.

Warunki Aharoniego – Haxella: najmniejsze zestawy przypinania

Mówimy, że zbiór $K$ krawędzi łączy inny zbiór $F$ krawędzi, jeśli każda krawędź w $F$ przecina jakąś krawędź w $K$ . Szerokość w hipergrafu $H = (V, E)$ , oznaczona jako $(H),$ jest najmniejszym rozmiarem podzbioru $E$ , który spina $E$ . Dopasowana szerokość hipergrafu $H$ , oznaczona jako $mw (H)$ , jest maksimum, spośród wszystkich dopasowań $M$ w $H$ , minimalnego rozmiaru podzbioru $E$ , który przypina $M$ . Ponieważ $E$ zawiera wszystkie dopasowania w $E$ , szerokość H jest oczywiście co najmniej tak duża, jak szerokość dopasowania $H$ .

Aharoni i Haxell udowodnili następujący warunek:

Niech $H = (X + Y, E)$ będzie dwudzielnym hipergrafem. Załóżmy, że dla każdego podzbioru $Y 0$ z $Y$ zachodzi następująca nierówność:

${\ Displaystyle mw (N_ {H} (Y_ {0})) \ geq | Y_ {0} |}$

[innymi słowy: $0 N H (Y)$ zawiera pasujące $0 M (Y)$ takie, że co najmniej $| Y 0 |$ rozłączne krawędzie z $0 N H (Y)$ są wymagane do przypięcia $0 M (Y)$ ]. Następnie $H$ przyznaje $Y$ -doskonałe dopasowanie.

Później rozszerzyli ten warunek na kilka sposobów, które zostały później rozszerzone przez Meszulama w następujący sposób:

Niech $H = (X + Y, E)$ będzie dwudzielnym hipergrafem. Załóżmy, że dla każdego podzbioru $Y 0$ z $Y$ zachodzi co najmniej jeden z następujących warunków:

${\ Displaystyle mw (N_ {H} (Y_ {0})) \ geq | Y_ {0} |}$ lub ${\ Displaystyle w (N_ {H} (Y_ {0})} \ geq 2 | Y_ {0} | -1}$

Następnie $H$ przyznaje $Y$ -doskonałe dopasowanie.

W prostych wykresach

W prostym grafie dwudzielnym hipergraf sąsiedztwa zawiera tylko singletony - singleton dla każdego sąsiada $Y 0$ . Ponieważ singletony nie przecinają się, cały zbiór sąsiadów $0 N H (Y)$ jest dopasowaniem, a jego jedynym zbiorem przypinania jest sam zbiór $0 N H (Y)$ , tj. szerokość dopasowania $0 N H (Y)$ to $| 0 N H (Y) |$ , a jego szerokość jest taka sama:

{\ Displaystyle w (N_ {H} (Y_ {0})) = mw (N_ {H} (Y_ {0})) = | N_ {H} (Y_ {0}) |.}

Zatem oba powyższe warunki są równoważne z warunkiem małżeństwa Halla.

Przykłady

Rozważamy kilka grafów dwudzielnych z $Y = {1, 2}$ i $X = {A, B; a, b, c}.$ Warunek Aharoniego-Haxella trywialnie obowiązuje dla zbioru pustego. Dotyczy to podzbiorów o rozmiarze 1 wtedy i tylko wtedy, gdy każdy wierzchołek w $Y$ jest zawarty w co najmniej jednej krawędzi, co łatwo sprawdzić. Pozostaje sprawdzić sam podzbiór $Y.$

$H = {{1,A,a}; {2,B,b}; {2,B,c} }.$ Tutaj $N H (Y) = { {A, a}, {B, b}, {B, c} }.$ Jego szerokość dopasowania wynosi co najmniej 2, ponieważ zawiera dopasowanie rozmiaru 2, np. ${{A,a}, {B,b}},$ którego nie można przypiąć żadną pojedynczą krawędzią z $0 N H (Y)$ . Rzeczywiście, H dopuszcza $Y$ , np. ${{1,A,a}; {2,B,b} }.$
$H = {{1,A,a}; {1,B,b}; {2,A,b}, {2,B,a} }.$ Tutaj $N H (Y) = { {A,a}, {B,b}, {A,b}, {B,a} }.$ Jego szerokość dopasowania wynosi 1: zawiera dopasowanie o rozmiarze 2, np. ${ {A,a}, {B,b} },$ ale to dopasowanie może być przypięte pojedynczą krawędzią, np. ${A,b}.$ Drugim dopasowaniem rozmiaru 2 jest ${{A,b},{B,a}},$ ale również można je przypiąć pojedynczą krawędzią ${A,a}.$ Podczas gdy $N H (Y)$ jest większy niż w przykładzie 1, jego szerokość dopasowania jest mniejsza - w szczególności jest mniejsza niż $| Y |$ . Zatem warunek wystarczający Aharoniego-Haxella nie jest spełniony. Rzeczywiście, $H$ nie dopuszcza idealnego dopasowania $Y.$
$H = {{1,A,a}, {1,A,b}; {1,B,a}, {1,B,b}; {2,A,a}, {2,A,b}; {2,B,a}, {2,B,b} }.$ Tutaj, podobnie jak w poprzednim przykładzie, $N H (Y) = { {A, a}, {B, b}, {A, b}, {B, a} }, więc warunek wystarczający$ Aharoniego-Haxella jest naruszony. Szerokość $N H (Y)$ wynosi 2, ponieważ jest przyszpilona np. przez zbiór ${ {A,a}, {B,b} },$ więc słabszy warunek Meszulama też jest naruszony. Jednak to $H$ dopuszcza idealne dopasowanie $Y$ , np. ${{1,A,a}; {2,B,b} },$ co pokazuje, że warunki te nie są konieczne.

Sformułowanie rodziny zestawów

Rozważmy dwudzielny hipergraf $H = (X + Y, E)$ gdzie $Y = {1, \dots, m}.$ Twierdzenia typu Halla nie dbają o sam zbiór $Y$ - dbają tylko o sąsiadów elementów $Y$ . Dlatego $H$ można przedstawić jako zbiór rodzin zbiorów ${H 1, \dots, H m},$ gdzie dla każdego $i$ w $[m]$ , $H i := N H ({i}) =$ rodzina zbiorów sąsiadów $i$ . Dla każdego podzbioru $Y 0$ z $Y$ rodzina zbiorów N $0 H (Y) jest$ sumą rodzin zbiorów $Hi i$ dla $w$ Y $. 0$ Idealnym dopasowaniem w $H$ jest rodzina zbiorów o rozmiarze $m$ , gdzie dla każdego $i$ w $[m]$ $Hi,$ rodzina zbiorów $Hi R$ jest reprezentowana przez zbiór $R i$ w , a zbiory reprezentatywne $i są$ rozłączne parami.

W tej terminologii twierdzenie Aharoniego – Haxella można sformułować w następujący sposób.

Niech $A = {H 1, \dots, H m}$ będzie zbiorem rodzin zbiorów. Dla każdego podzbioru $B$ z $A$ rozważ zbiór-rodzinę $\cup B$ - sumę wszystkich $H i$ w $B$ . Załóżmy, że dla każdego podzbioru $B zbioru$ A ten $\cup B$ zawiera pasujące $M (B) takie$ $,$ że co najmniej $| B. |$ rozłączne podzbiory z $\cup B$ są wymagane do przypięcia $M (B)$ . Wtedy $A$ dopuszcza system rozłącznych przedstawicieli.

Warunek konieczny i wystarczający

Niech $H = (X + Y, E)$ będzie dwudzielnym hipergrafem. Następujące są równoważne:

$H$ przyznaje $Y$ - idealne dopasowanie.
Istnieje przypisanie pasującego $0 M (Y)$ w $0 NH | (Y)$ dla każdego podzbioru $Y 0 |$ $z 0$ Y $,$ tak że przypięcie $0 M (Y)$ wymaga co najmniej rozłączne krawędzie z $\cup {M (Y 1): Y 1$ jest podzbiorem $Y 0}.$

W sformułowaniu rodziny zbiorów: niech $A = {H 1, \dots, H m}$ będzie zbiorem rodzin zbiorów. Następujące są równoważne:

$A$ dopuszcza system rozłącznych przedstawicieli;
Istnieje przypisanie pasującego $M (B$ w $\cup B$ dla każdego podzbioru $B$ z $A$ , tak że dla przypięcia $M (B)$ przynajmniej $| B |$ krawędzie z $\cup {M (C): C$ jest podzbiorem z $B}$ są wymagane.

Przykłady

Rozważmy przykład nr 3 powyżej: $H = { {1,A,a}, {1,A,b};$ ${1,B,a}, {1,B,b};$ ${2,A,a}, {2,A,b};$ ${2,B,a}, {2,B,b} }.$ Ponieważ dopuszcza idealne dopasowanie $Y$ , musi spełniać warunek konieczny. Rzeczywiście, rozważ następujące przypisanie do podzbiorów $Y$ :

$M({1}) = {A,a}$
$M({2}) = {B,b}$
$M({1,2}) = { {A, a}, {B, b} }$

W warunku wystarczającym przypięcie $M({1,2})$ wymagało co najmniej dwóch krawędzi z $N H (Y) = { {A,a}, {B,b}, {A,b}, {B,a} } ;$ nie trzymało.

Ale w koniecznym warunku przypięcie $M({1,2})$ wymagało co najmniej dwóch krawędzi z $M({1}) \cup M({2}) \cup M({1,2}) = { {A,a} , {B,b}};$ to trzyma.

Zatem warunek konieczny + wystarczający jest spełniony.

Dowód

Dowód jest topologiczny i wykorzystuje lemat Spernera . Co ciekawe, implikuje to nowy dowód topologiczny dla pierwotnego twierdzenia Halla.

Po pierwsze, załóżmy, że żadne dwa wierzchołki w $Y nie$ mają dokładnie tego samego sąsiada (jest to bez utraty ogólności, ponieważ dla każdego elementu $y$ z $Y$ można dodać fikcyjny wierzchołek do wszystkich sąsiadów z $y$ ).

Niech $Y = {1, \dots, m}.$ Rozważają $m$ -vertex simplex i dowodzą, że dopuszcza ona triangulację $T$ z pewnymi specjalnymi właściwościami, które nazywają triangulacją ekonomiczno-hierarchiczną . Następnie oznaczają każdy wierzchołek $T$ hiperkrawędzią z $N H (Y)$ w następujący sposób:

(a) Dla każdego $i$ w $Y$ , główny wierzchołek $i$ simpleksu jest oznaczony hiperkrawędzią z pasującego $M({i})$ .
(b) Każdy wierzchołek $T$ na ścianie rozpiętej przez podzbiór $Y 0$ z $Y$ jest oznaczony hiperkrawędzią z pasującego $0 M(Y)$ .
(c) Dla każdych dwóch sąsiednich wierzchołków $T$ ich etykiety są albo identyczne, albo rozłączne.

Ich wystarczający stan oznacza, że takie oznakowanie istnieje. Następnie kolorują każdy wierzchołek $v$ T kolorem $i tak$ $,$ że hiperkrawędź przypisana do $v$ jest sąsiadem $i$ .

Warunki (a) i (b) gwarantują, że to zabarwienie spełnia warunek brzegowy Spernera. Dlatego istnieje w pełni oznakowany simpleks. W tym simpleksie jest $m$ hiperkrawędzi, z których każda sąsiaduje z innym i tylko jed- norodnym elementem $Y$ , więc muszą być rozłączne. Jest to pożądane dopasowanie idealne $Y.$

Rozszerzenia

Twierdzenie Aharoni – Haxell ma wersję niedoboru. Służy do udowodnienia hipotezy Rysera dla $r = 3$ .

Warunki Meszulama - topologiczne twierdzenia Halla

W abstrakcyjnych uproszczonych kompleksach

Niech $V$ będzie zbiorem wierzchołków. Niech $C$ będzie abstrakcyjnym kompleksem uproszczonym na $V$ . Niech $V y$ (dla $y$ w $Y$ ) będą podzbiorami $V$ . CV $-$ transwersalny to zbiór w $C$ (element $C$ ), którego przecięcie z każdym $V y$ zawiera dokładnie jeden wierzchołek. Dla każdego podzbioru $Y 0$ z $Y$ niech

{\ Displaystyle V_ {Y_ {0}}: = \ bigcup _ {y \ w Y_ {0}} V_ {y}.}

$wynosi$ że dla każdego podzbioru $Y 0$ z $Y łączność$ homologiczna plus 2 podzespołu indukowanego przez co najmniej $| Y 0 |$ , to jest:

{\ Displaystyle \ eta _ {H} (C [V_ {Y_ {0}}]) \ geq | Y_ {0} |.}

Wtedy istnieje $CV-$ poprzeczny. To znaczy: istnieje zbiór w $C$ , który przecina każdy $V y$ o dokładnie jeden element. To twierdzenie ma wersję niedostateczną. Jeśli dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle \ eta _ {H} (C [V_ {Y_ {0}}]) \ geq | Y_ {0} | -d,}

wtedy istnieje częściowa $C$ -poprzeczna, która przecina pewne $| Y | - d$ o 1 element, a pozostałe o co najwyżej 1 element. Bardziej ogólnie, jeśli $g$ jest funkcją dodatnich liczb całkowitych spełniających $g (z + 1) \leq g (z) + 1$ i dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle \ eta _ {H} (C [V_ {Y_ {0}}]) \ geq g (| Y_ {0} |), }

wtedy istnieje zbiór w $C$ , który przecina co najmniej $g (| Y |)$ z $V y$ o jeden element, a pozostałe o co najwyżej jeden element.

Gra Meszulama

Korzystanie z powyższego twierdzenia wymaga pewnych dolnych granic łączności homologicznej. Jedną z takich dolnych granic wyznacza gra Meszulama . Jest to gra rozgrywana przez dwóch graczy na wykresie. Jeden gracz - CON - chce udowodnić, że graf ma wysoką spójność homologiczną . Drugi gracz – NON – chce udowodnić, że jest inaczej. CON oferuje krawędzie NON jeden po drugim; NON może albo rozłączyć krawędź, albo ją eksplodować; eksplozja usuwa punkty końcowe krawędzi i wszystkich ich sąsiadów. Wynik CON to liczba eksplozji, gdy znikną wszystkie wierzchołki, lub nieskończoność, jeśli pozostaną pojedyncze wierzchołki. Wartość gry na danym wykresie $G$ (wynik KON, gdy obaj gracze grają optymalnie) jest oznaczony przez $Ψ(G)$ . Liczby tej można użyć, aby uzyskać dolną granicę homologicznej łączności kompleksu niezależności G $,$ oznaczonego : ${\ Displaystyle {\ mathcal {I}} (G)}$ :

{\ Displaystyle \ eta _ {H} ({\ mathcal {I}} (G)} \ geq \ psi (G).}

Dlatego powyższe twierdzenie implikuje, co następuje. Niech $V$ będzie zbiorem wierzchołków. Niech $G$ będzie grafem na $V$ . Załóżmy, że dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle \ Psi (G [V_ {Y_ {0}}]) \ geq | Y_ {0} |.}

Wtedy istnieje niezależny zbiór w $G$ , który przecina każdy $V y$ o dokładnie jeden element.

W prostych grafach dwudzielnych

Niech $H$ będzie grafem dwudzielnym z częściami $X$ i $Y$ . Niech $V$ będzie zbiorem krawędzi H $.$ Niech $G = L(H =$ $)$ wykres liniowy H . Wtedy kompleks $_$ zespołowi H ${\ Displaystyle {\ mathcal {M}} (H)}$ . Jest to uproszczony kompleks na krawędziach $H$ , którego elementami są wszystkie dopasowania na $H$ . Dla każdego wierzchołka $y$ w $Y$ niech $V y$ będzie zbiorem krawędzi przylegających do $y$ (zauważ, że $V y$ jest podzbiorem $V$ ). Następnie dla każdego podzbioru $Y 0$ z $Y$ indukowany podwykres ${\ Displaystyle G [V_ {Y_ {0}}]}$ zawiera klikę dla każdego sąsiada $Y 0$ (wszystkie krawędzie sąsiadujące z $Y 0$ , które spotykają się w tym samym wierzchołku $X$ , tworzą klikę na wykresie liniowym). Więc są $| 0 N H (Y) |$ rozłączne kliki. Dlatego, gdy gra Meszulam, NON potrzebuje $| 0 N H (Y) |$ eksplozje, które zniszczą wszystkie $0 L(N H (Y))$ , więc $Ψ(L(N H 0 (Y)) = | 0 N H (Y) |$ . Tak więc stan Meszulama

{\ Displaystyle \ psi (G [V_ {Y_ {0}}]) \ geq | Y_ {0} |}

jest równoważne z warunkiem małżeństwa Halla. Tutaj zbiory $V y$ są parami rozłączne, więc $C$ -przekrojowy zawiera unikalny element z każdego $V y$ , co jest równoważne dopasowaniu nasycającemu $Y.$

W pasujących kompleksach

Niech $H$ będzie hipergrafem dwudzielnym i załóżmy, że $C$ jest jego pasującym kompleksem ${\ Displaystyle {\ mathcal {M}} (H)}$ . Niech $H y$ (dla $y$ w $Y$ ) będzie zbiorem krawędzi $H$ . Dla każdego podzbioru $Y 0$ Y , ${\ Displaystyle {\ mathcal {M}} (H_ {Y_ {0}})}$ $jest$ zbiorem dopasowań w podhipergrafie:

{\ Displaystyle \ bigcup _ {y \ w Y_ {0}} H_ {y}.}

Jeśli dla każdego podzbioru $Y 0$ z $Y$ :

{\ Displaystyle \ eta _ {H} ({\ mathcal {M}} (H_ {Y_ {0}})) \ geq | Y_ {0} |}

Wtedy istnieje dopasowanie, które przecina każdy zestaw $H y$ dokładnie raz (jest to również nazywane dopasowaniem tęczowym , ponieważ każdy $H y$ może być traktowany jako kolor).

$prawdą$ w szczególności, jeśli zdefiniujemy $H y$ jako zbiór krawędzi $H$ zawierających wierzchołek $y$ Y . W tym przypadku ${\ Displaystyle {\ mathcal {M}} (H_ {Y_ {0}})}$ jest równoważne z $0 N H (Y)$ - multihipergrafem sąsiadów $Y 0$ („multi” - ponieważ każdy sąsiad może pojawić się kilka razy dla kilku różnych $y$ ).

Dopasowany kompleks hipergrafu jest dokładnie kompleksem niezależności jego wykresu liniowego , oznaczonym jako $L (H)$ . To jest graf, w którym wierzchołki są krawędziami $H$ , a dwa takie wierzchołki są połączone, jeśli ich odpowiadające krawędzie przecinają się w $H$ . Dlatego powyższe twierdzenie implikuje:

{\ Displaystyle \ eta _ {H} ({\ mathcal {M}} (H)} \ geq \ Psi (L (H))

Połączenie poprzednich nierówności prowadzi do następującego warunku.

Niech

H = (X + Y, E)

będzie dwudzielnym hipergrafem. Załóżmy, że dla każdego podzbioru

Y 0

z

Y

spełniony jest następujący warunek:

{\ Displaystyle \ Psi (L (N_ {H} (Y_ {0})}) \ geq | Y_ {0} |,}

gdzie

0 N H (Y)

jest uważany za multihipergraf (tj. może zawierać tę samą hiperkrawędź kilka razy, jeśli jest sąsiadem kilku różnych elementów

Y 0

). Następnie

H

przyznaje

Y

-doskonałe dopasowanie.

Przykłady

Rozważamy kilka hipergrafów dwudzielnych z $Y = {1, 2}$ i $X = {A, B; a, b, c}.$ Warunek Meszulam trywialnie obowiązuje dla zbioru pustego. Odnosi się to do podzbiorów o rozmiarze 1, jeśli sąsiedni wykres każdego wierzchołka w $Y$ nie jest pusty (a więc wymaga co najmniej jednej eksplozji do zniszczenia), co łatwo sprawdzić. Pozostaje sprawdzić sam podzbiór $Y.$ S

$H = {{1,A,a}; {2,B,b}; {2,B,c} }.$ Tutaj $N H (Y) = { {A, a}, {B, b}, {B, c} }.$ Graf $L(N H (Y))$ ma trzy wierzchołki: $Aa, Bb, Bc.$ Tylko dwa ostatnie są połączone; wierzchołek Aa jest izolowany. Stąd $Ψ(L(N H (Y)) = \infty$ Rzeczywiście, $H$ dopuszcza idealne dopasowanie $Y$ , np. ${{1,A,a}; {2,B,b}}.$
H = {{1,A,a}; {1,B,b}; {2,A,b}, {2,B,a} }. Tutaj $L(N H (Y))$ ma cztery wierzchołki: $Aa, Bb, Ab, Ba$ i cztery krawędzie: ${Aa,Ab}, {Aa,Ba}, {Bb,Ba}, {Bb,Ab}.$ Dla dowolnej krawędzi, którą oferuje CON, NON może ją eksplodować i zniszczyć wszystkie wierzchołki. Stąd $Ψ(L(NH nie (Y)) = 1.$ Rzeczywiście, $H$ dopuszcza idealnego dopasowania $Y.$
$H = {{1,A,a}, {1,A,b};$ ${1,B,a}, {1,B,b};$ ${2,A,a}, {2,A,b};$ ${2,B,a}, {2,B,b} }.$ Tutaj $N H (Y)$ jest takie samo jak w poprzednim przykładzie, więc warunek dostateczny Meszulama jest naruszony. Jednak to $H$ dopuszcza idealne dopasowanie $Y$ , np. ${{1,A,a}; {2,B,b} },$ co pokazuje, że warunek ten nie jest konieczny.

Nie jest znany warunek konieczny i wystarczający przy użyciu $Ψ$ .

Więcej warunków z tęczowych dopasowań

Dopasowanie tęczy to dopasowanie na prostym wykresie, w którym każda krawędź ma inny „kolor”. Traktując kolory jako wierzchołki w zbiorze $Y$ , można zobaczyć, że dopasowanie tęczy jest w rzeczywistości dopasowaniem w dwudzielnym hipergrafie . Zatem kilka warunków wystarczających dla istnienia dużego dopasowania tęczowego można przetłumaczyć na warunki istnienia dużego dopasowania w hipergrafie.

Poniższe wyniki odnoszą się do trójdzielnych hipergrafów , w których każda z 3 części zawiera dokładnie $n$ wierzchołków, stopień każdego wierzchołka wynosi dokładnie $n$ , a zbiór sąsiadów każdego wierzchołka jest dopasowany (odtąd „ $n$ -trójdzielny-hipergraf”) :

Każdy $n$ -trójdzielny hipergraf ma dopasowanie o rozmiarze $2 n ⁄ 3$ .
Każdy $n$ -trójdzielny-hipergraf ma dopasowanie o rozmiarze $n - \sqrt n$ .
Każdy $n$ -trójdzielny-hipergraf ma dopasowanie o rozmiarze $n - 11 log 22 (n)$ .
HJ Ryser przypuszczał, że gdy $n$ jest nieparzyste , każdy $n$ -trójdzielny-hipergraf ma dopasowanie o rozmiarze $n$ .
SK Stein i Brualdi przypuszczali, że gdy $n$ jest parzyste , każdy $n$ -trójdzielny-hipergraf ma dopasowanie o rozmiarze $n - 1$ . (wiadomo, że dopasowanie rozmiaru $n$ może w tym przypadku nie istnieć).
Bardziej ogólne przypuszczenie Steina jest takie, że dopasowanie o rozmiarze $n - 1$ istnieje nawet bez wymogu, aby zbiór sąsiadów każdego wierzchołka w $Y$ był dopasowaniem.

Następujące wyniki dotyczą bardziej ogólnych hipergrafów dwudzielnych:

Dowolny hipergraf trójdzielny $(X 1 + X 2 + Y, E),$ w którym $| Y | = 2 n - 1$ , stopień każdego wierzchołka $y$ w $Y$ wynosi $n$ , a zbiór sąsiadów $y$ jest dopasowaniem, ma dopasowanie rozmiaru $n$ . 2 $| n - 1$ jest najlepsze z możliwych: $jeśli Y | = 2 n - 2$ , to maksymalne dopasowanie może mieć rozmiar $n$ -1.
Dowolny hipergraf dwudzielny $(X + Y, E)$ , w którym $| Y | = 3 n - 2$ , stopień każdego wierzchołka y w $Y$ wynosi $n$ , a zbiór sąsiadów $y$ jest dopasowaniem, ma dopasowanie o rozmiarze $n$ . Nie wiadomo, czy to najlepsze z możliwych. Dla parzystego $n$ wiadomo tylko, że wymagane jest $2 n ;$ dla nieparzystego $n$ wiadomo tylko, że $2 n - 1$ jest wymagany.

Zobacz też

Zestaw niezależny od tęczy

Warunek Conforti-Cornuejols-Kapoor-Vuskovic: Zrównoważone hipergrafy

Zrównoważony hipergraf jest alternatywnym uogólnieniem grafu dwudzielnego: jest to hipergraf, w którym każdy nieparzysty cykl $C$ z $H$ ma krawędź zawierającą co najmniej trzy wierzchołki $C$ .

Niech $H = (V, E)$ będzie zrównoważonym hipergrafem. Następujące są równoważne:

$H$ dopuszcza idealne dopasowanie (tj. dopasowanie, w którym każdy wierzchołek jest dopasowany).
Dla wszystkich rozłącznych zbiorów wierzchołków $V 1$ , $V 2$ , jeśli $| V 1 | > | V 2 |$ , to istnieje krawędź $e$ w $E$ taka, że $| mi \cap V 1 | > | mi \cap V 2 |$ (równoważnie: jeśli $| e \cap V 2 | \geq | e \cap V 1 |$ dla wszystkich krawędzi $e$ w $E$ , potem $| V 2 | \geq | V 1 |$ ).

W prostych wykresach

Prosty graf jest dwudzielny, jeśli jest zrównoważony (nie zawiera cykli nieparzystych ani krawędzi z trzema wierzchołkami).

Niech $G = (X + Y, E) będzie grafem dwudzielnym. Niech X 0 będzie podzbiorem X i Y 0 podzbiorem Y . Warunek " e \cap X 0 \geq | e \cap Y 0 |$ dla wszystkich krawędzi $e$ w $E$ " oznacza, że $X 0$ zawiera wszystkich sąsiadów wierzchołków $Y 0-$ Zatem warunek CCKV przyjmuje postać:

„Jeśli podzbiór $X 0$ z $X$ zawiera zbiór $0 N H (Y)$ , to $| X 0 | \geq | Y 0 |$ ”.

Jest to równoważne z warunkiem Halla.

Zobacz też

Dopasowania doskonałe w hipergrafach wysokiego stopnia - przedstawia inne warunki wystarczające dla istnienia dopasowań doskonałych, które opierają się wyłącznie na stopniu wierzchołków.

^ ^a ^b ^c Aharoni, Ron; Kessler, Ofra (15.10.1990). „O możliwym rozszerzeniu twierdzenia Halla na hipergrafy dwudzielne” . Matematyka dyskretna . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
^ ^a ^b Kessler, Ofra (1989). Dopasowania w hipergrafach (praca doktorska) . Hajfa, Izrael: Technion, izraelski instytut technologiczny.
^ ^a ^b Aharoni, Ron (1985-12-01). „Dopasowania inn-partiten-graphs” . Grafy i kombinatoryka . 1 (1): 303–304. doi : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .
^ ^a ^b ^c Aharoni, Ron (1993-06-01). „O kryterium dopasowywalności w hipergrafach”. Grafy i kombinatoryka . 9 (2): 209–212. doi : 10.1007/BF02988309 . ISSN 1435-5914 . S2CID 29126477 .
^ ^{ab Haxell,}^PE (1995-09-01). „Warunek dopasowania w hipergrafach”. Grafy i kombinatoryka . 11 (3): 245–248. doi : 10.1007/bf01793010 . S2CID 28459229 .
^ ^a ^b ^c ^d ^e Aharoni, Ron; Haxell, Penny (2000). „Twierdzenie Halla dla hipergrafów” . Dziennik teorii grafów . 35 (2): 83–88. doi : 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V . ISSN 1097-0118 .
^ ^abc ^{Meszulam , Roy}⁽ 2001-01-01). „Kompleks kliki i dopasowanie hipergrafu”. Kombinatoryka . 21 (1): 89–94. doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
Bibliografia _ _ _ _ : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1
Bibliografia _ Feige Uriel; Saberi Amin (2012-07-24). „Święty Mikołaj spotyka dopasowania hipergrafów” . Transakcje ACM na algorytmach . 8 (3): 1–9. doi : 10.1145/2229163.2229168 . S2CID 10281304 .
Bibliografia _ Kalaitzis Christos; Svensson Ola (2017-05-26). „Algorytm kombinatoryczny dla ograniczonej uczciwej alokacji maks.-min.”. Transakcje ACM na algorytmach . 13 (3): 1–28. ar Xiv : 1409.0607 . doi : 10.1145/3070694 . S2CID 14749011 .
Bibliografia _ Rothvoss, Thomas; Zhang, Yihao (23.12.2019), „A Tale of Santa Claus, Hypergraphs and Matroids”, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms , Proceedings, Society for Industrial and Applied Mathematics, s. 2748–2757, doi : 10.1137/1.9781611975994.167 , ISBN 978-1-61197-599-4 , S2CID 49880727
^ ^ab ^Aharoni , Ron (2001-01-01). „Hipoteza Rysera dla trójdzielnych 3-wykresów”. Kombinatoryka . 21 (1): 1–4. doi : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .
^ Kalai, Gil (25.11.2012). „Wszystkiego najlepszego Ronie Aharoni!” . Kombinatoryka i nie tylko . Źródło 2020-06-30 .
^ ^ab ^Meszulam , Roy (2003-05-01). „Liczby dominacji i homologii” . Dziennik teorii kombinatorycznej . Seria A. 102 (2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .
Bibliografia _ Berger, Eli; Briggs, Józef; Segal-Halevi, Erel; Zerbib, Shira (2020-11-02). „Ułamkowo zrównoważone hipergrafy i tęczowe twierdzenia KKM”. arXiv : 2011.01053 [ matematyka. CO ].
^ Koksma, Klaas K. (1969-07-01). „Dolna granica rzędu częściowego przekroju poprzecznego w kwadracie łacińskim” . Dziennik teorii kombinatorycznej . 7 (1): 94–95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .
Bibliografia _ „Kwadrat łaciński n × n ma przekrój poprzeczny z co najmniej n-n różnymi symbolami” . Dziennik teorii kombinatorycznej . Seria A. 24 (2): 235–237. doi : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .
Bibliografia _ Shor, Peter W. (2008-10-01). „Dolna granica długości częściowego przekroju poprzecznego w kwadracie łacińskim” . Dziennik teorii kombinatorycznej . Seria A. 115 (7): 1103–1113. doi : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .
^ ^ab ^Aharoni , Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). „Na przypuszczenia Steina”. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. doi : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .
^ Stein, Sherman (1975-08-01). „Poprzeczne kwadratów łacińskich i ich uogólnienia” . Pacific Journal of Mathematics . 59 (2): 567–575. doi : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .
^ ^ab ^Aharoni , Ron; Berger, Eli (2009-09-25). „Tęczowe dopasowania w $r$-Partite $r$-Graphs” . Elektroniczny Dziennik Kombinatoryki . 16 (1). doi : 10.37236/208 . ISSN 1077-8926 .
^ Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). „Doskonałe dopasowania w zrównoważonych hipergrafach”. Kombinatoryka . 16 (3): 325–329. doi : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .
Bibliografia _ Triesch, Eberhard (2002-07-01). „Idealne dopasowanie w zrównoważonych hipergrafach - podejście kombinatoryczne”. kombinatoryka . 22 (3): 409–416. doi : 10.1007/s004930200020 . ISSN 1439-6912 . S2CID 34490040 .

[:1-1] Aharoni, Ron; Kessler, Ofra (15.10.1990). „O możliwym rozszerzeniu twierdzenia Halla na hipergrafy dwudzielne” . Matematyka dyskretna . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .

[:2-2] Kessler, Ofra (1989). Dopasowania w hipergrafach (praca doktorska) . Hajfa, Izrael: Technion, izraelski instytut technologiczny.

[:5-3] Aharoni, Ron (1985-12-01). „Dopasowania inn-partiten-graphs” . Grafy i kombinatoryka . 1 (1): 303–304. doi : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .

[:3-4] Aharoni, Ron (1993-06-01). „O kryterium dopasowywalności w hipergrafach”. Grafy i kombinatoryka . 9 (2): 209–212. doi : 10.1007/BF02988309 . ISSN 1435-5914 . S2CID 29126477 .

[:0-5] {ab Haxell,}^PE (1995-09-01). „Warunek dopasowania w hipergrafach”. Grafy i kombinatoryka . 11 (3): 245–248. doi : 10.1007/bf01793010 . S2CID 28459229 .

[:4-6] Aharoni, Ron; Haxell, Penny (2000). „Twierdzenie Halla dla hipergrafów” . Dziennik teorii grafów . 35 (2): 83–88. doi : 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V . ISSN 1097-0118 .

[:7-7] {Meszulam , Roy}⁽ 2001-01-01). „Kompleks kliki i dopasowanie hipergrafu”. Kombinatoryka . 21 (1): 89–94. doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

[8] Bibliografia _ _ _ _ : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1

[9] Bibliografia _ Feige Uriel; Saberi Amin (2012-07-24). „Święty Mikołaj spotyka dopasowania hipergrafów” . Transakcje ACM na algorytmach . 8 (3): 1–9. doi : 10.1145/2229163.2229168 . S2CID 10281304 .

[10] Bibliografia _ Kalaitzis Christos; Svensson Ola (2017-05-26). „Algorytm kombinatoryczny dla ograniczonej uczciwej alokacji maks.-min.”. Transakcje ACM na algorytmach . 13 (3): 1–28. ar Xiv : 1409.0607 . doi : 10.1145/3070694 . S2CID 14749011 .

[11] Bibliografia _ Rothvoss, Thomas; Zhang, Yihao (23.12.2019), „A Tale of Santa Claus, Hypergraphs and Matroids”, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms , Proceedings, Society for Industrial and Applied Mathematics, s. 2748–2757, doi : 10.1137/1.9781611975994.167 , ISBN 978-1-61197-599-4 , S2CID 49880727

[:6-12] Aharoni , Ron (2001-01-01). „Hipoteza Rysera dla trójdzielnych 3-wykresów”. Kombinatoryka . 21 (1): 1–4. doi : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .

[13] Kalai, Gil (25.11.2012). „Wszystkiego najlepszego Ronie Aharoni!” . Kombinatoryka i nie tylko . Źródło 2020-06-30 .

[:03-14] Meszulam , Roy (2003-05-01). „Liczby dominacji i homologii” . Dziennik teorii kombinatorycznej . Seria A. 102 (2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .

[15] Bibliografia _ Berger, Eli; Briggs, Józef; Segal-Halevi, Erel; Zerbib, Shira (2020-11-02). „Ułamkowo zrównoważone hipergrafy i tęczowe twierdzenia KKM”. arXiv : 2011.01053 [ matematyka. CO ].

[16] Koksma, Klaas K. (1969-07-01). „Dolna granica rzędu częściowego przekroju poprzecznego w kwadracie łacińskim” . Dziennik teorii kombinatorycznej . 7 (1): 94–95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .

[17] Bibliografia _ „Kwadrat łaciński n × n ma przekrój poprzeczny z co najmniej n-n różnymi symbolami” . Dziennik teorii kombinatorycznej . Seria A. 24 (2): 235–237. doi : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .

[18] Bibliografia _ Shor, Peter W. (2008-10-01). „Dolna granica długości częściowego przekroju poprzecznego w kwadracie łacińskim” . Dziennik teorii kombinatorycznej . Seria A. 115 (7): 1103–1113. doi : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .

[:022-19] Aharoni , Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). „Na przypuszczenia Steina”. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. doi : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .

[20] Stein, Sherman (1975-08-01). „Poprzeczne kwadratów łacińskich i ich uogólnienia” . Pacific Journal of Mathematics . 59 (2): 567–575. doi : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .

[:02-21] Aharoni , Ron; Berger, Eli (2009-09-25). „Tęczowe dopasowania w $r$-Partite $r$-Graphs” . Elektroniczny Dziennik Kombinatoryki . 16 (1). doi : 10.37236/208 . ISSN 1077-8926 .

[22] Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). „Doskonałe dopasowania w zrównoważonych hipergrafach”. Kombinatoryka . 16 (3): 325–329. doi : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .

[23] Bibliografia _ Triesch, Eberhard (2002-07-01). „Idealne dopasowanie w zrównoważonych hipergrafach - podejście kombinatoryczne”. kombinatoryka . 22 (3): 409–416. doi : 10.1007/s004930200020 . ISSN 1439-6912 . S2CID 34490040 .