Perfektní shoda v hypergrafech vysokého stupně - Perfect matching in high-degree hypergraphs

v teorie grafů, perfektní shoda v hypergrafech vysokého stupně je cesta výzkumu, kterou se snažíte najít dostatečné podmínky za existenci a perfektní shoda v hypergrafu, pouze na základě stupeň vrcholů nebo jejich podmnožin.

Úvod

Stupně a shody v grafech

Jednoduše graf G = (PROTI, E), stupeň vrcholu proti, často označované deg (proti) nebo δ (proti), je počet hran v E přilehlý k proti. Minimální stupeň grafu, často označovaný stupnicí (G) nebo δ (proti), je minimum stupně (proti) přes všechny vrcholy proti v PROTI.

A vhodný v grafu je sada hran tak, že každý vrchol sousedí nejvýše s jednou hranou; A perfektní shoda je shoda, ve které každý vrchol sousedí přesně s jednou hranou. Dokonalé přizpůsobení nemusí vždy existovat, a proto je zajímavé najít dostatečné podmínky, které zaručují jeho existenci.

Jedna taková podmínka vyplývá z Diracova věta o Hamiltonových cyklech. Říká se, že pokud deg (G) ≥ n/ 2, pak graf připouští a Hamiltonovský cyklus; to znamená, že připouští perfektní shodu. Faktor n/ 2 je těsný, protože kompletní bipartitní graf na (n/2-1, n/ 2 + 1) vrcholy mají titul n/ 2-1, ale nepřipouští perfektní shodu.

Výsledky popsané níže mají za cíl rozšířit tyto výsledky z grafů na hypergrafy.

Stupně v hypergrafech

V hypergrafu H = (V, E), každá hrana E může obsahovat více než dva vrcholy PROTI. Stupeň vrcholu proti v PROTI je, stejně jako dříve, počet hran v E které obsahují proti. Ale v hypergrafu můžeme také zvážit stupeň podmnožiny vrcholů: dána podmnožina U z PROTI, deg (U) je počet hran v E které obsahují Všechno vrcholy U. Stupeň hypergrafu lze tedy definovat různými způsoby v závislosti na velikosti podmnožin, jejichž stupeň je považován.

Formálně pro každé celé číslo d ≥ 1, deg_d(H) je minimum stupně (U) přes všechny podmnožiny U z V, které obsahují přesně d vrcholy. Tedy deg₁(H) odpovídá definici stupně jednoduchého grafu, konkrétně nejmenšího stupně jediného vrcholu; deg₂(H) je nejmenší stupeň z dvojice vrcholů; atd.

Hypergraf H = (PROTI, E) je nazýván r-jednotný pokud každý hyperedge E obsahuje přesně r vrcholy PROTI. v r-jednotné grafy, příslušné hodnoty d jsou 1, 2, ..., r-1. V jednoduchém grafu r=2.

Podmínky na 1-vrcholném stupni

Několik autorů prokázalo dostatečné podmínky pro případ d= 1, tj. Podmínky na nejmenším stupni jediného vrcholu.

• Li H je 3 uniformní hypergraf na n vrcholy, n je násobkem 3 a ${ displaystyle deg _ {1} (H) geq { bigg (} 5/9 + o (1) { bigg)} {n zvolit 2}}$, pak H obsahuje perfektní shodu.^[1]
• Li H je 3 uniformní hypergraf na n vrcholy, n je násobkem 3 a ${ displaystyle deg _ {1} (H) geq {n-1 vyberte 2} - {2n / 3 vyberte 2} +1}$, pak H obsahuje perfektní shodu - shodu velikosti k. Tento výsledek je nejlepší možný.^[2]
• Li H je 4 uniformní hypergraf s on n vrcholy, n je násobkem 4 a ${ displaystyle deg _ {1} (H) geq {n-1 vyberte 3} - {3n / 4 vyberte 3}}$, pak H obsahuje perfektní shodu - shodu velikosti k. Tento výsledek je nejlepší možný.^[3]
• Li H je r-uniform, n je násobek r, a ${ displaystyle deg _ {1} (H)> { frac {r-1} {r}} vlevo ({{ binom {n-1} {r-1}} - { binom {n- kr-1} {r-1}}} vpravo)}$, pak H obsahuje alespoň odpovídající velikost k+1. Zejména nastavení k=n/r-1 dává, pokud ${ displaystyle deg _ {1} (H)> { frac {r-1} {r}} vlevo ({{ binom {n-1} {r-1}} - 1} vpravo)}$, pak H obsahuje perfektní shodu.^[4]
• Li H je r-jednotka a r-partita, každá strana obsahuje přesně n vrcholy a ${ displaystyle deg _ {1} (H)> { frac {r-1} {r}} vlevo ({n ^ {r-1} - (nk) ^ {r-1}} vpravo) }$, pak H obsahuje alespoň odpovídající velikost k+1. Zejména nastavení k=n-1 dává, že pokud ${ displaystyle deg _ {1} (H)> { frac {r-1} {r}} vlevo ({n ^ {r-1} -1} vpravo)}$, pak H obsahuje perfektní shodu.^[4]

Pro srovnání, Diracova věta o Hamiltonových cyklech říká, že pokud H je 2 uniformní (tj. jednoduchý graf) a ${ displaystyle deg _ {1} (H) geq {n-1 vyberte 1} - {n / 2 vyberte 1} + 1 = n / 2}$, pak H připouští perfektní shodu.

Podmínky na (r-1) -tuple stupeň

Několik autorů prokázalo dostatečné podmínky pro případ d=r-1, tj. Podmínky na nejmenším stupni množin r-1 vrcholy, v r-jednotné hypergrafy s n vrcholy.

v r-část r-jednotné hypergrafy

Následující výsledky se týkají r- částečné hypergrafy, které mají přesně n vrcholy na každé straně (rn celkové vrcholy):

• Li n≥ 1000 a ${ displaystyle deg _ {r-1} (H) geq n / 2 + { sqrt {2n log _ {2} n}}}$, pak H má perfektní shodu. Tento výraz je nejmenší možný až do termínu nižšího řádu; zejména, n/ 2 nestačí.^[5]
• Li ${ displaystyle deg _ {r-1} (H) geq n / r}$, pak H připouští shodu, která pokrývá všechny, ale maximálně r-2 vrcholy v každé třídě vrcholů H. The n/r faktor je v podstatě nejlepší možný.^[5]
• Nechat PROTI₁,...,PROTI_r být r strany H. Pokud stupeň každého (r-1) -tuple in PROTI\PROTI₁ je přísně větší než n/ 2 a stupeň každého (r-1) -tuple in PROTI\PROTI_r je alespoň n/ 2 tedy H připouští perfektní shodu. ^[6]

Obecně r-jednotné hypergrafy

• Pro každé γ> 0, když n je dostatečně velký, pokud ${ displaystyle deg _ {r-1} (H) geq (1/2 + gamma) n}$ pak H je Hamiltonian, a tedy obsahuje perfektní shodu.^[7]
• Li n je dostatečně velký a ${ displaystyle deg _ {r-1} (H) geq n / 2 + 3r ^ {2} { sqrt {n log _ {2} n}}}$, pak H připouští perfektní shodu.^[5]
• Li ${ displaystyle deg _ {r-1} (H) geq n / r + 3r ^ {2} { sqrt {n log _ {2} n}}}$, pak H připouští shodu, která pokrývá všechny kromě maximálně 2r² vrcholy. ^[5]
• Když n je dělitelné r a dostatečně velká, prahová hodnota je ${ displaystyle deg _ {r-1} (H) geq n / 2-r + c_ {k, n}}$, kde C_{k, n} je konstanta v závislosti na paritě n a k (všechny níže uvedené výrazy jsou nejlepší možné):^[8]
  • 3 když r / 2 je sudé an / r je liché;
  • 5/2, když r je liché a (n-1) / 2 je liché;
  • 3/2, když r je liché a (n-1) / 2 je sudé;
  • 2 jinak.
• Když n není dělitelné r, dostatečný stupeň se blíží n/r: -li ${ displaystyle deg _ {r-1} (H) geq n / r + O ( log (n))}$ pak H připouští perfektní shodu. Výraz je téměř nejmenší možný: nejmenší možný je ${ displaystyle lfloor n / r rfloor}$. ^[8]

Jiné podmínky

Existují dostatečné podmínky pro další hodnoty d:

• Pro všechny d ≥ r / 2, práh pro deg_d(H) je blízko ${ displaystyle left ({ frac {1} {2}} + o (1) right) { binom {n} {r-d}}}$.^[9]
• Pro všechny d < r / 2, práh pro deg_d(H) je maximálně ${ displaystyle left ({ frac {r-d} {r}} + o (1) right) { binom {n-d} {r-d}}}$.^[1]
• Pokud H je r-partita a každá strana obsahuje přesně n vrcholy a ${ displaystyle deg _ {d} (H) geq { frac {r-d} {r}} n ^ {r-d} + rn ^ {r-d-1}}$, pak H obsahuje shodu pokrývající všechny kromě (d-1)r vrcholy.^[1]
• Li n je dostatečně velký a dělitelný r, a ${ displaystyle deg _ {d} (H) geq { frac {rd} {r}} { binom {n} {rd}} + r ^ {r + 1} ( ln {n}) ^ {1/2} n ^ {rd-1/2}}$, pak H obsahuje shodu pokrývající všechny kromě (d-1)r vrcholy.^[1]

Viz také

• Hallovy věty pro hypergrafy - uvádí další dostatečné podmínky pro existenci dokonalých shody v hypergrafech, obdobně jako Hallova manželská věta.

Reference