Perfekt matchning i höggradiga hypergrafer

Inom grafteorin är perfekt matchning i höggradiga hypergrafer en forskningsväg som försöker hitta tillräckliga förutsättningar för existensen av en perfekt matchning i en hypergraf, endast baserat på graden av hörn eller delmängder av dem.

Introduktion

Grader och matchningar i grafer

I en enkel graf $G = (V, E)$ är graden av en vertex $v$ , ofta betecknad med $deg(v)$ eller $δ(v)$ , antalet kanter i $E$ intill $v$ . Den minsta graden av en graf, ofta betecknad med $deg(G)$ eller $δ(v)$ , är minimum av $deg(v)$ över alla hörn $v$ i $V$ .

En matchning i en graf är en uppsättning kanter så att varje vertex ligger intill högst en kant; en perfekt matchning är en matchning där varje vertex ligger intill exakt en kant. En perfekt matchning finns inte alltid, och därför är det intressant att hitta tillräckliga förutsättningar som garanterar dess existens.

Ett sådant villkor följer av Diracs teorem om Hamiltons cykler . Det står att, om $.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} deg( G ) ≥ n ⁄ 2$ , så medger grafen en Hamiltonsk cykel ; detta innebär att det medger en perfekt matchning. Faktorn $n ⁄ 2$ är snäv, eftersom den fullständiga tvådelade grafen på $(n ⁄ 2 - 1, n ⁄ 2 + 1)$ hörn har grad $n ⁄ 2 - 1$ men inte medger en perfekt matchning.

Resultaten som beskrivs nedan syftar till att utöka dessa resultat från grafer till hypergrafer .

Grader i hypergrafer

I en hypergraf $H = (V, E)$ kan varje kant av $E innehålla mer än$ två hörn av $V.$ Graden av en vertex $v$ i $V$ är, som tidigare, antalet kanter i $E$ som innehåller $v$ . Men i en hypergraf kan vi också överväga graden av delmängder av hörn : givet en delmängd $U$ av $V är$ $deg(U)$ antalet kanter i $E$ som innehåller alla hörn av $U$ . Graden av en hypergraf kan således definieras på olika sätt beroende på storleken på delmängder vars grad beaktas.

Formellt, för varje heltal $d \geq 1$ , är $deg d (H)$ minimum av $deg(U)$ över alla delmängder $U$ av $V$ som innehåller exakt $d$ hörn. $Grad 1 (H) motsvarar$ alltså definitionen av en grad av en enkel graf, nämligen den minsta graden av en enda vertex; $deg 2 (H)$ är den minsta graden av ett par hörn; etc.

En hypergraf $H = (V, E)$ kallas $r$ -uniform om varje hyperkant i $E$ innehåller exakt $r$ hörn av $V.$ I $r- uniforma grafer$ är de relevanta värdena för $d$ $1, 2, \dots , r - 1$ . I en enkel graf är $r = 2$ .

Förhållanden på 1-vertex grad

Flera författare visade tillräckliga förhållanden för fallet $d = 1$ , dvs förhållanden på den minsta graden av en enda vertex.

Om $H$ är en 3-enhetlig hypergraf på $n$ hörn, är $n$ en multipel av 3, och
$\deg _{1}(H)\geq {\bigg (}5/9+o(1){ \bigg )}{n \choose 2},$

då innehåller $H$ en perfekt matchning.
Om $H$ är en 3-enhetlig hypergraf på $n$ hörn, är $n$ en multipel av 3, och
$\deg _{1}(H)\geq {n-1 \choose 2}-{2n/ 3 \välj 2}+1,$

då innehåller $H$ en perfekt matchning - en matchning av storlek $k$ . Detta resultat är det bästa möjliga.
Om $H$ är en 4-enhetlig hypergraf med $n$ hörn, är $n$ en multipel av 4, och
$\deg _{1}(H)\geq {n-1 \choose 3}-{3n/4 \ välj 3},$

då innehåller $H$ en perfekt matchning - en matchning av storlek $k$ . Detta resultat är det bästa möjliga.
Om $H$ är $r$ -uniform är n en multipel av $r$ , och
$\deg _{1}(H)>{\frac {r-1}{r}}\left({{\binom {n-1}{r-1}}-{\binom {n-kr-1}{r-1}}}\right),$

då innehåller $H$ en matchning av storleken minst $k + 1$ . I synnerhet ger inställningen $k = n ⁄ r - 1 att, if$

$\deg _{1}(H)>{\frac {r-1}{r}}\ vänster({{\binom {n-1}{r-1}}-1}\höger),$

då innehåller $H$ en perfekt matchning.
Om $H$ är $r$ -uniform och $r$ -partit, innehåller varje sida exakt $n$ hörn, och
$\deg _{1}(H)>{\frac {r-1}{r }}\left({n^{r-1}-(nk)^{r-1}}\right),$

då innehåller $H$ en matchning av storleken minst $k + 1$ . Speciellt ger inställningen $k = n - 1$ att if

$\deg _{1}(H)>{\frac {r-1}{r}}\left({n ^{r-1}-1}\höger),$

då innehåller $H$ en perfekt matchning.

Som jämförelse säger Diracs sats om Hamiltons cykler att om $H$ är 2-uniform (dvs en enkel graf) och

\deg _{1}(H)\geq {n-1 \choose 1}- {n/2 \choose 1}+1=n/2,

då erkänner $H$ en perfekt matchning.

Villkor för (r-1)-tuppelgrad

Flera författare bevisade tillräckliga villkor för fallet $d = r - 1$ , dvs villkor på den minsta graden av uppsättningar av $r - 1$ hörn, i $r$ -uniforma hypergrafer med $n$ hörn.

I r -partite r -uniforma hypergrafer

Följande resultat relaterar till $r$ -partite hypergrafer som har exakt $n$ hörn på varje sida ( $rn$ hörn totalt):

Om ${\displaystyle \deg _{r-1}(H)\geq n/2+{\sqrt {2n\log _{$
och $n \geq 1000$ , då har $H$ en perfekt matchning. Detta uttryck är minst möjligt upp till termen av lägre ordning; i synnerhet $n ⁄ 2$ inte tillräckligt.
Om $\deg _{r-1}(H)\geq n/r$
sedan medger $H$ en matchning som täcker alla utom högst $r - 2$ hörn i varje hörnklass av $H$ . n $. ⁄ r-$ faktorn är i princip den bästa möjliga
Låt $V 1, \dots , V r$ vara de $r$ sidorna av $H$ . Om graden av varje $(r - 1)$ -tuppel i $V ⁄ V 1$ är strikt större än $n ⁄ 2$ , och graden av varje $(r - 1)$ -tuppel i $V ⁄ V r$ är minst $n ⁄ 2$ , så $H$ erkänner en perfekt matchning.

I allmänhet r -uniforma hypergrafer

För varje $γ > 0$ , när $n$ är tillräckligt stor, if
$\deg _{r-1}(H)\geq (1/2+\gamma )n$

då är $H$ Hamiltonian, och innehåller alltså en perfekt matchning.
Om $(H)\geq n/2+3r^{2}{\sqrt {n\log _{2}n}}}$
och $n$ är tillräckligt stor, då medger $H$ en perfekt matchning.
Om $\deg _{r-1}(H)\geq n/r+3r^{2}{\ sqrt {n\log _{2}n}},$
sedan medger $H$ en matchning som täcker alla utom högst $2 r 2$ hörn.
När n är delbart med r och tillräckligt stor är tröskeln
$\deg _{r-1}(H)\geq n/2-r+c_{k,n}$

där $c k, n$ är en konstant beroende på pariteten för $n$ och $k$ (alla uttryck nedan är de bästa möjliga):
- 3 när $r ⁄ 2$ är jämnt och $n ⁄ r$ är udda;
- 5 ⁄ 2 när $r$ är udda och $(n -1) ⁄ 2$ är udda;
- 3 ⁄ 2 när $r$ är udda och $(n -1) ⁄ 2$ är jämnt;
- 2 annars.
När $n$ inte är delbart med $r$ är den tillräckliga graden nära $n ⁄ r$ : om $deg r -1 (H) \geq n ⁄ r + O (log(n))$ , då medger $H$ en perfekt matchning. Uttrycket är nästan det minsta möjliga: det minsta möjliga är $⌊ n ⁄ r ⌋$ .

Andra förhållanden

Det finns några tillräckliga villkor för andra värden på $d$ :

För alla $d \geq r ⁄ 2 är$ tröskeln för $deg d (H)$ nära:
$\left({\frac {1}{2}}+o(1)\right){\binom {n}{rd}}.$
För alla $d < r ⁄ 2 är$ tröskeln för $deg d (H)$ högst:
$\left({\frac {rd}{r}}+o(1)\right){\binom {nd}{ rd}}$
Om $H$ är $r$ -partit och varje sida innehåller exakt $n$ hörn, och
$\deg _{d}(H)\geq {\frac {rd}{r}}n^ {rd}+rn^{rd-1},$

då innehåller $H$ en matchning som täcker alla utom $(d - 1) r$ hörn.
Om $n$ är tillräckligt stor och delbar med $r$ , och
$\deg _{d}(H )\geq {\frac {rd}{r}}{\binom {n}{rd}}+r^{r+1}(\ln {n})^{1/2}n^{rd-1 /2},$

då innehåller $H$ en matchning som täcker alla utom $(d - 1) r$ hörn.

Se även

Hall-typ satser för hypergrafer - listar andra tillräckliga villkor för förekomsten av perfekta matchningar i hypergrafer, analogt med Halls äktenskapssats.

^ ^a ^b ^c ^d Hàn, Höft; Person, Yury; Schacht, Mathias (2009-01-01). "Om perfekta matchningar i enhetliga hypergrafer med stor minsta vertexgrad". SIAM Journal on Discrete Mathematics . 23 (2): 732–748. doi : 10.1137/080729657 . ISSN 0895-4801 .
^ Khan, Imdadullah (2013-01-01). "Perfekta matchningar i 3-uniforma hypergrafer med stor vertexgrad". SIAM Journal on Discrete Mathematics . 27 (2): 1021–1039. doi : 10.1137/10080796X . ISSN 0895-4801 . S2CID 18434210 .
^ Khan, Imdadullah (2016-01-01). "Perfekt matchning i 4-uniforma hypergrafer" . Journal of Combinatorial Theory, serie B . 116 : 333-366. doi : 10.1016/j.jctb.2015.09.005 . ISSN 0095-8956 .
^ ^a ^b Daykin, David E.; Häggkvist, Roland (1981-02-01). "Grader som ger oberoende kanter i en hypergraf" . Bulletin från Australian Mathematical Society . 23 (1): 103–109. doi : 10.1017/S0004972700006924 . ISSN 1755-1633 .
^ ^a ^b ^c ^d Kühn, Daniela; Osthus, Deryk (2006). "Matchningar i hypergrafer av stor minimigrad". Journal of Graph Theory . 51 (4): 269–280. doi : 10.1002/jgt.20139 . ISSN 1097-0118 . S2CID 6769560 .
^ Aharoni, Ron; Georgakopoulos, Agelos; Sprüssel, Philipp (2009-01-01). "Perfekt matchningar i r-partite r-grafer" . European Journal of Combinatorics . 30 (1): 39–42. arXiv : 0911.4008 . doi : 10.1016/j.ejc.2008.02.011 . ISSN 0195-6698 . S2CID 1092170 .
^ Rödl, Vojtěch; Szemerédi, Endre; Ruciński, Andrzej (2008-03-01). "En ungefärlig Dirac-typsats för k-uniforma hypergrafer". Combinatorica . 28 (2): 229–260. doi : 10.1007/s00493-008-2295-z . ISSN 1439-6912 . S2CID 5799411 .
^ ^a ^b Rödl, Vojtech; Ruciński, Andrzej; Szemerédi, Endre (2009-04-01). "Perfekt matchningar i stora enhetliga hypergrafer med stor minsta kollektiv grad" . Journal of Combinatorial Theory, serie A . 116 (3): 613–636. doi : 10.1016/j.jcta.2008.10.002 . ISSN 0097-3165 .
^ Pikhurko, Oleg (2008-09-01). "Perfekta matchningar och K 4 3 -Tilings i hypergrafer av stor kodgrans". Grafer och kombinatorik . 24 (4): 391–404. doi : 10.1007/s00373-008-0787-7 . ISSN 0911-0119 . S2CID 29248979 .

[:3-1] Hàn, Höft; Person, Yury; Schacht, Mathias (2009-01-01). "Om perfekta matchningar i enhetliga hypergrafer med stor minsta vertexgrad". SIAM Journal on Discrete Mathematics . 23 (2): 732–748. doi : 10.1137/080729657 . ISSN 0895-4801 .

[2] Khan, Imdadullah (2013-01-01). "Perfekta matchningar i 3-uniforma hypergrafer med stor vertexgrad". SIAM Journal on Discrete Mathematics . 27 (2): 1021–1039. doi : 10.1137/10080796X . ISSN 0895-4801 . S2CID 18434210 .

[3] Khan, Imdadullah (2016-01-01). "Perfekt matchning i 4-uniforma hypergrafer" . Journal of Combinatorial Theory, serie B . 116 : 333-366. doi : 10.1016/j.jctb.2015.09.005 . ISSN 0095-8956 .

[:4-4] Daykin, David E.; Häggkvist, Roland (1981-02-01). "Grader som ger oberoende kanter i en hypergraf" . Bulletin från Australian Mathematical Society . 23 (1): 103–109. doi : 10.1017/S0004972700006924 . ISSN 1755-1633 .

[:0-5] Kühn, Daniela; Osthus, Deryk (2006). "Matchningar i hypergrafer av stor minimigrad". Journal of Graph Theory . 51 (4): 269–280. doi : 10.1002/jgt.20139 . ISSN 1097-0118 . S2CID 6769560 .

[6] Aharoni, Ron; Georgakopoulos, Agelos; Sprüssel, Philipp (2009-01-01). "Perfekt matchningar i r-partite r-grafer" . European Journal of Combinatorics . 30 (1): 39–42. arXiv : 0911.4008 . doi : 10.1016/j.ejc.2008.02.011 . ISSN 0195-6698 . S2CID 1092170 .

[7] Rödl, Vojtěch; Szemerédi, Endre; Ruciński, Andrzej (2008-03-01). "En ungefärlig Dirac-typsats för k-uniforma hypergrafer". Combinatorica . 28 (2): 229–260. doi : 10.1007/s00493-008-2295-z . ISSN 1439-6912 . S2CID 5799411 .

[:1-8] Rödl, Vojtech; Ruciński, Andrzej; Szemerédi, Endre (2009-04-01). "Perfekt matchningar i stora enhetliga hypergrafer med stor minsta kollektiv grad" . Journal of Combinatorial Theory, serie A . 116 (3): 613–636. doi : 10.1016/j.jcta.2008.10.002 . ISSN 0097-3165 .

[:2-9] Pikhurko, Oleg (2008-09-01). "Perfekta matchningar och K 4 3 -Tilings i hypergrafer av stor kodgrans". Grafer och kombinatorik . 24 (4): 391–404. doi : 10.1007/s00373-008-0787-7 . ISSN 0911-0119 . S2CID 29248979 .