Idealne dopasowanie w hipergrafach wysokiego stopnia

W teorii grafów idealne dopasowanie w hipergrafach wysokiego stopnia jest drogą badawczą mającą na celu znalezienie warunków wystarczających do istnienia idealnego dopasowania w hipergrafie , w oparciu jedynie o stopień wierzchołków lub ich podzbiorów.

Wstęp

Stopnie i dopasowania na wykresach

W prostym grafie G = ( V , E ) stopień wierzchołka v , często oznaczany przez deg ( v ) lub δ ( v ) , jest liczbą krawędzi w E sąsiadujących z v . Minimalny stopień grafu, często oznaczany jako deg( G ) lub δ( v ) , to minimum deg( v ) nad wszystkimi wierzchołkami v w V. _

Dopasowanie w grafie to zbiór krawędzi takich, że każdy wierzchołek sąsiaduje co najwyżej z jedną krawędzią ; idealne dopasowanie to dopasowanie, w którym każdy wierzchołek sąsiaduje dokładnie z jedną krawędzią. Idealne dopasowanie nie zawsze istnieje, dlatego interesujące jest znalezienie wystarczających warunków, które gwarantują jego istnienie.

Jeden taki warunek wynika z twierdzenia Diraca o cyklach Hamiltona . Mówi, że jeśli deg( G ) ≥ n ⁄ 2 , to wykres dopuszcza cykl Hamiltona ; oznacza to, że dopuszcza idealne dopasowanie. Współczynnik n ⁄ 2 jest ścisły, ponieważ pełny graf dwudzielny na wierzchołkach ( n ⁄ 2 – 1, n 2 1 + 1) ma stopień n ⁄ 2 – ale nie dopuszcza idealnego dopasowania.

Wyniki opisane poniżej mają na celu rozszerzenie tych wyników z wykresów na hipergrafy .

Stopnie w hipergrafach

W hipergrafie H = ( V , E) każda krawędź E może zawierać więcej niż dwa wierzchołki V . Stopień wierzchołka v w V jest, jak poprzednio, liczbą krawędzi w E , które zawierają v . Ale w hipergrafie możemy również wziąć pod uwagę stopień podzbiorów wierzchołków: dany podzbiór U z V , deg( U ) to liczba krawędzi w E , które zawierają wszystkie wierzchołki U. _ Zatem stopień hipergrafu można zdefiniować na różne sposoby w zależności od wielkości podzbiorów, których stopień jest brany pod uwagę.

Formalnie dla każdej liczby całkowitej d ≥ 1 deg _d ( H ) jest minimum deg ( U ) nad wszystkimi podzbiorami U z V , które zawierają dokładnie d wierzchołków. Zatem deg ₁ ( H ) odpowiada definicji stopnia grafu prostego, czyli najmniejszego stopnia pojedynczego wierzchołka; deg ₂ ( H ) to najmniejszy stopień pary wierzchołków; itp.

Hipergraf H = ( V , E ) nazywamy r -jednostajnym , jeśli każda hipergraf w E zawiera dokładnie r wierzchołków V . W r -jednostajnych odpowiednie wartości d wynoszą 1, 2, … , r – 1 . Na prostym wykresie r = 2 .

Warunki na stopniu 1 wierzchołka

Kilku autorów udowodniło warunki wystarczające dla przypadku d = 1 , tj. warunki na najmniejszym stopniu pojedynczego wierzchołka.

• Jeśli H jest 3-jednolitym hipergrafem na n wierzchołkach, n jest wielokrotnością 3 i

  ${\ Displaystyle \ stopień _ {1} (H) \ geq {\ bigg (} 5/9 + o (1) { \bigg )}{n \wybierz 2},}$

  wtedy H zawiera idealne dopasowanie.

• Jeśli H jest 3-jednolitym hipergrafem na n wierzchołkach, n jest wielokrotnością 3 i

  ${\ Displaystyle \ stopień _ {1} (H) \ geq {n-1 \ wybierz 2} - {2n / 3 \wybierz 2}+1,}$

  wtedy H zawiera idealne dopasowanie - dopasowanie o rozmiarze k . Ten wynik jest najlepszy z możliwych.

• Jeśli H jest 4-jednolitym hipergrafem z n wierzchołkami, n jest wielokrotnością 4 i

  ${\ Displaystyle \ stopień _ {1} (H) \ geq {n-1 \ wybierz 3} - {3n/4 \ wybierz 3},}$

  wtedy H zawiera idealne dopasowanie - dopasowanie o rozmiarze k . Ten wynik jest najlepszy z możliwych.

• Jeśli H jest r -jednolity, n jest wielokrotnością r i

  ${\ Displaystyle \ deg _ {1} (H)> {\ Frac {r-1}{r}}\left({{\binom {n-1}{r-1}}-{\binom {n-kr-1}{r-1}}}\right),}$

  wtedy H zawiera dopasowanie o rozmiarze co najmniej k + 1 . W szczególności ustawienie k = n ⁄ r – 1 daje, że jeśli

  ${\ Displaystyle \ stopień _ {1} (H)> {\ Frac {r-1} {r}} \ lewo({{\binom {n-1}{r-1}}-1}\prawo),}$

  wtedy H zawiera idealne dopasowanie.

• Jeśli H jest r -jednolity i r -częściowy, to każdy bok zawiera dokładnie n wierzchołków i

  ${\ Displaystyle \ deg _ {1} (H)> {\ Frac {r-1} {r }}\lewo({n^{r-1}-(nk)^{r-1}}\prawo),}$

  wtedy H zawiera dopasowanie o rozmiarze co najmniej k + 1 . W szczególności ustawienie k = n – 1 daje, że jeśli

  ${\ Displaystyle \ stopień _ {1} (H)> {\ Frac {r-1} {r}} \ lewo ({n ^{r-1}-1}\prawo),}$

  wtedy H zawiera idealne dopasowanie.

Dla porównania, twierdzenie Diraca o cyklach Hamiltona mówi, że jeśli H jest 2-jednostajny (tj. prosty wykres) i

${\ Displaystyle \ stopień _ {1} (H) \ geq {n-1 \ wybrać 1} - {n/2 \wybierz 1}+1=n/2,}$

wtedy H przyznaje idealne dopasowanie.

Warunki na (r-1)-stopniu

Kilku autorów udowodniło warunki wystarczające dla przypadku d = r – 1 , czyli warunki na najmniejszym stopniu zbiorów r – 1 wierzchołków, w r -jednostajnych hipergrafach o n wierzchołkach.

W r -partite r -jednolite hipergrafy

Poniższe wyniki odnoszą się do r -częściowych hipergrafów, które mają dokładnie n wierzchołków po każdej stronie ( łącznie rn wierzchołków):

• Jeśli ${\ Displaystyle \ deg _ {r-1} (H) \ geq n/2 + {\ sqrt {2n \ log _ {2 }N}}}$

  i n ≥ 1000 , to H ma idealne dopasowanie. To wyrażenie jest najmniejsze z możliwych aż do terminu niższego rzędu; w szczególności n / 2 nie jest wystarczające.

• Jeśli ${\ Displaystyle \ deg _ {r-1} (H) \ geq n/r}$

  wtedy H dopuszcza dopasowanie, które obejmuje wszystkie, ale co najwyżej r – 2 wierzchołki w każdej klasie wierzchołków H . Współczynnik n / r jest zasadniczo najlepszy z możliwych.

• Niech V ₁ , … , V _r będą r bokami H . Jeśli stopień każdej ( r – 1) -krotki w V / V ₁ jest ściśle większy niż n / 2 , a stopień każdej ( r – 1) -krotki w V / V _r wynosi co najmniej n / 2 , to H przyznaje idealne dopasowanie.

W ogólności r -jednolite hipergrafy

• Dla każdego γ > 0 , gdy n jest wystarczająco duże, jeśli

  ${\ Displaystyle \ stopień _ {r-1} (H) \ geq (1/2 + \ gamma) n}$

  wtedy H jest hamiltonianem, a zatem zawiera idealne dopasowanie.

• Jeśli ${\ Displaystyle \ deg _ {r-1} (H) \ geq n/2 + 3r ^ {2} {\ sqrt {n\log _{2}n}}}$

  a n jest wystarczająco duże, to H dopuszcza idealne dopasowanie.

• Jeśli ${\ Displaystyle \ deg _ {r-1} (H) \ geq n / r + 3r ^ {2} {\ sqrt {n\log _{2}n}},}$

  wtedy H dopuszcza dopasowanie, które obejmuje wszystkie wierzchołki oprócz co najwyżej 2 r ² .

• Gdy n jest podzielne przez r i wystarczająco duże, próg wynosi

  ${\ Displaystyle \ deg _ {r-1} (H) \ geq n / 2-r + c_ {k, n}}$

  gdzie c _{k , n} jest stałą zależną od parzystości n i k (wszystkie poniższe wyrażenia są najlepsze z możliwych):

  • 3, gdy r / 2 jest parzyste, a n / r jest nieparzyste;
  • 5 / 2 , gdy r jest nieparzyste i ( n -1) / 2 jest nieparzyste;
  • 3 / 2 , gdy r jest nieparzyste i ( n -1) / 2 jest parzyste;
  • 2 inaczej.
• Kiedy n nie jest podzielne przez r , wystarczający stopień jest bliski n ⁄ r : jeśli degr _{r -1} ( H ) ≥ n ⁄ r + O (log( n )) , to H dopuszcza idealne dopasowanie. Wyrażenie jest prawie najmniejsze z możliwych: najmniejsze możliwe to ⌊ n ⁄ r ⌋ .

Inne warunki

Istnieją pewne warunki wystarczające dla innych wartości d :

• Dla wszystkich d ≥ r ⁄ 2 próg dla deg _d ( H ) jest bliski:

  ${\ Displaystyle \ lewo ({\ Frac {1} {2}} + o (1) \ prawo) {\ binom {n} {rd}}.}$

• Dla wszystkich d < r ⁄ 2 próg dla deg _d ( H ) wynosi co najwyżej:

  ${\ Displaystyle \ lewo ({\ Frac {rd} {r}} + o (1) \ prawej) {\ binom {nd} r & D}}}$

• Jeśli H jest r -częściowa i każdy bok zawiera dokładnie n wierzchołków, i

  ${\ Displaystyle \ deg _ {d} (H) \ geq {\ Frac {rd} {r}} n ^ {rd}+rn^{rd-1},}$

  wtedy H zawiera dopasowanie obejmujące wszystkie wierzchołki oprócz ( d – 1) r .

• Jeśli n jest wystarczająco duże i podzielne przez r , i

  ${\ Displaystyle \ stopień _ {d} (H. )\geq {\frac {rd}{r}}{\binom {n}{rd}}+r^{r+1}(\ln {n})^{1/2}n^{rd-1 /2},}$

  wtedy H zawiera dopasowanie obejmujące wszystkie wierzchołki oprócz ( d – 1) r .

Zobacz też

• Twierdzenia typu Halla dla hipergrafów - wymienia inne warunki wystarczające dla istnienia doskonałych dopasowań w hipergrafach, analogiczne do twierdzenia Halla o małżeństwie.