Rysers dohad - Rysers conjecture - Wikipedia

v teorie grafů, Ryserova domněnka je domněnka týkající se maximální velikosti shody a minimální příčné velikosti v hypergrafy.

Tato domněnka se poprvé objevila v roce 1971 v Ph.D. práce J. R. Hendersona, jehož poradcem byl Herbert John Ryser.^[1]

Předkola

A vhodný v hypergrafii je sada hyper-hran, takže se každý vrchol objevuje nejvýše v jednom z nich. Největší velikost shody v hypergrafu H je označen ${ displaystyle nu (H)}$.

A příčný (nebo vrcholový kryt) v hypergrafii je sada vrcholů, takže každý hyperedge obsahuje alespoň jeden z nich. Nejmenší velikost příčného v hypergrafu H je označen ${ displaystyle tau (H)}$.

Pro každého H, ${ displaystyle nu (H) leq tau (H)}$, protože každá obálka musí obsahovat alespoň jeden bod z každé hrany v jakékoli shodě.

Pokud H je r-jednotka (každý hyperedge má přesně r vrcholy) ${ displaystyle tau (H) leq r cdot nu (H)}$, protože sjednocení hran z libovolného maximálního párování je maximálně sada rv vrcholy, které splňují všechny hrany.

Domněnka

Ryserova domněnka je, že pokud H není jen r- uniforma, ale také r-partite (tj. jeho vrcholy lze rozdělit na.) r sady, takže každá hrana obsahuje přesně jeden prvek každé sady), pak:

${ displaystyle tau (H) leq (r-1) cdot nu (H)}$

Tj. Multiplikativní faktor ve výše uvedené nerovnosti lze snížit o 1.^[2]

Extrémní hypergrafy

An extremální hypergraf k Ryserově domněnce je hypergraf, ve kterém se domněnka drží rovnosti, tj. ${ displaystyle tau (H) = (r-1) cdot nu (H)}$. Existence takových hypergrafů ukazuje, že faktor r-1 je nejmenší možný.

Příkladem extremálního hypergrafu je zkrácená projektivní rovina - projektivní rovina řádu r-1, ve kterém je odstraněn jeden vrchol a všechny řádky, které jej obsahují.^[3] Je známo, že existuje kdykoli r-1 je síla prvočísla.

Existují i ​​další rodiny takových extrémních hypergrafů.^[4]

Speciální případy

V případě r= 2, hypergraf se stává a bipartitní graf a domněnka se stává ${ displaystyle tau (H) leq nu (H)}$. Je známo, že to je pravda Kőnigova věta.

V případě r= 3, domněnka byla prokázána Ron Aharoni.^[5] Důkaz používá Aharoni-Haxellova věta pro shodu v hypergrafech.

V případech r= 4 a r= 5, následující slabší verze byla prokázána Penny Haxell a Scott:^[6] existuje nějaká ε> 0 taková, že

${ displaystyle tau (H) leq (r- varepsilon) cdot nu (H)}$.

Navíc v případech r= 4 a r= 5, Ryserova domněnka byla ve zvláštním případě prokázána Tuzou (1978) ${ displaystyle nu (H) = 1}$, tj.:

${ Displaystyle nu (H) = 1 implikuje tau (H) leq r-1}$.

Frakční varianty

A zlomková shoda v hypergrafu je přiřazení váhy ke každému hyperedge tak, že součet hmotností blízko každého vrcholu je nanejvýš jeden. Největší velikost zlomkové shody v hypergrafu H je označen ${ displaystyle nu ^ {*} (H)}$.

A zlomek příčný v hypergrafu je přiřazení váhy každému vrcholu tak, že součet hmotností v každém hyperedge je alespoň jeden. Nejmenší velikost zlomku příčného v hypergrafu H je označen ${ displaystyle tau ^ {*} (H)}$. To naznačuje i dualita lineárního programování ${ displaystyle nu ^ {*} (H) = tau ^ {*} (H)}$.

Furedi prokázal následující zlomkovou verzi Ryserova domněnky: If H je r-partite a r-pravidelný (každý vrchol se zobrazuje přesně r hyperedges)^[7]

${ displaystyle tau ^ {*} (H) leq (r-1) cdot nu (H)}$.

Lovasz to ukázal^[8]

${ displaystyle tau (H) leq { frac {r} {2}} cdot nu ^ {*} (H)}$.

Reference