Problém Oberwolfachu

Nevyřešené problémy v matematice : Pro jakýkoli 2-regulární vrcholový graf lze celý graf rozložit na kopie s disjunktními okraji grafu ?

G

n

K_n

G

Oberwolfachovský problém je nevyřešený matematický problém, který lze formulovat jako problém alokace míst pro večeře, nebo abstraktněji jako problém teorie grafů o pokrytí úplných grafů cykly hran . Problém byl pojmenován po Oberwolfachském matematickém institutu , kde problém formuloval v roce 1967 Gerhard Ringel [1] .

Formulace

Na konferencích konaných v Oberwolfachu je zvykem společně stolovat v místnosti s kulatými stoly, které nejsou všechny stejně velké a místa u stolů se mění z oběda na večeři. Oberwolfachský problém se ptá, jak specifikovat rozdělení míst u stolů tak, aby všechna místa byla obsazena a všechny dvojice účastníků konference seděly vedle sebe pouze jednou. Instance úlohy může být označena jako , kde určuje velikosti tabulek. Případně, když se některé velikosti stolů opakují, může se to projevit jako horní index, například popis problému se třemi stoly pro pět míst [1] . $OP(x,y,z,\tečky )$ $x,y,z,\dots$ $OP(5^{3})$

Když je problém formulován jako problém teorie grafů, páry lidí sedících vedle sebe u konkrétní večeře mohou být reprezentovány jako spojení neprotínajících se (po okrajích) cyklů určité délky, jeden cyklus pro každý jídelní stůl. Toto spojení cyklů je 2-pravidelný graf a každý 2-pravidelný graf má tento tvar. Pokud je takový 2-regulární graf a má vrcholy, je otázka položena následovně: lze celý graf reprezentovat jako sjednocení kopií grafu, které se neprotíná podél hran [1] . $C_{x}+C_{y}+C_{z}+\cdots$ $G$ $n$ $K_n$ $G$

Aby řešení existovalo, musí být celkový počet účastníků konference (nebo ekvivalentně celkový počet míst u stolů nebo celkový počet vrcholů daných cyklů) liché číslo. Při každé večeři sedí účastník vedle dvou dalších účastníků, takže celkový počet sousedů každého účastníka musí být sudý, a to je možné pouze v případě, že je celkový počet účastníků lichý. Problém však může být rozšířen na sudé hodnoty , pokud se ptáte na tyto , zda je možné pokrýt všechny hrany kompletního grafu, kromě dokonalé shody, kopiemi daného 2-regulárního grafu. Stejně jako párový problém (další matematický problém o sezení u jídelního stolu) lze i tuto variantu problému formulovat za předpokladu, že účastníci večeře jsou rozděleni do manželských párů a že každý účastník musí s každým dalším účastníkem večeřet přesně jednou, kromě manžela (manželky) [2] . $n$ $n$ $n$ $n/2$

Pozoruhodné výsledky

Jsou známy pouze následující případy problému Oberwolfach, o kterých je známo, že nemají žádné řešení: , , a . Všeobecně se má za to, že všechny ostatní případy řešení ano, ale zatím se ukázalo, že řešitelné byly pouze speciální případy. $OP(3^{2})$ $OP(3^{4})$ $OP(4,5)$ $OP(3,3,5)$

Případy, pro které jsou známá řešení:

Všechny případy kromě a [3] [4] [5] [6] [2] . $OP(x^{y})$ $OP(3^{2})$ $OP(3^{4})$
Všechny případy, kdy mají všechny cykly sudou délku [3] [7] .
Všechny instance (kromě známých výjimek) od [8] . $n\leqslant 40$
Všechny instance pro některé patřící do nekonečné množiny prvočísel [9] [10] . $n$
Všechny případy kromě známých výjimek a [11] . $OP(x,y)$ $OP(3,3)$ $OP(4,5)$

Související úkoly

Kirkmanův problém školačky : Seskupení patnácti školaček do řad po třech sedmi různými způsoby tak, aby každá dvojice dívek byla mezi prvními třemi pouze jednou, je zvláštním případem problému Oberwolfach . Problém hamiltonovského rozkladu úplného grafu je dalším speciálním případem [7] . $OP(3^{5})$ $K_n$ $OP(n)$

Alspachova domněnka o rozkladu kompletního grafu na cykly daných velikostí souvisí s problémem Oberwolfach, ale nejde o zvláštní případy. Pokud je 2-pravidelný graf s vrcholy tvořenými neprotínajícími se cykly určité délky, pak řešení Oberwolfachovy úlohy pro dává rozklad celého grafu na kopie každého cyklu grafu . Ne každý rozklad na tolik cyklů každé velikosti však lze seskupit do disjunktních cyklů, které tvoří kopie , ale na druhou stranu ne každý případ Alspachovy domněnky zahrnuje sadu cyklů, které mají kopie každého cyklu. $G$ $n$ $G$ $(n-1)/2$ $G$ $K_n$ $G$ $(n-1)/2$

Poznámky

↑ 1 2 3 Hanfried Lenz, Gerhard Ringel . Stručný přehled o matematickém díle Egmonta Köhlera // Diskrétní matematika . - 1991. - T. 97 , čís. 1-3 . — S. 3–16 . - doi : 10.1016/0012-365X(91)90416-Y .
↑ 1 2 Charlotte Huang, Anton Kotzig, Alexander Rosa. O variaci problému Oberwolfach // Diskrétní matematika. - 1979. - T. 27 , no. 3 . — S. 261–277 . - doi : 10.1016/0012-365X(79)90162-6 .
↑ 1 2 Roland Häggkvist. Lema o cyklických rozkladech // Cykly v grafech (Burnaby, BC, 1982). - North-Holland, 1985. - T. 115. - S. 227-232. - (North-Holland Math. Stud.). - doi : 10.1016/S0304-0208(08)73015-9 .
↑ Brian Alspach, Roland Häggkvist. Několik postřehů k problému Oberwolfach // Journal of Graph Theory . - 1985. - T. 9 , no. 1 . — S. 177–187 . - doi : 10.1002/jgt.3190090114 .
↑ Brian Alspach, Schellenberg PJ, Stinson DR, David Wagner. Oberwolfachský problém a faktory cyklů jednotné liché délky // Journal of Combinatorial Theory . - 1989. - T. 52 , čís. 1 . — S. 20–43 . - doi : 10.1016/0097-3165(89)90059-9 .
↑ Hoffman DG, Schellenberg PJ Existence -faktorizace // diskrétní matematiky . - 1991. - T. 97 , čís. 1-3 . — S. 243–250 . - doi : 10.1016/0012-365X(91)90440-D . $C_{k}$ $K_{2n}-F$
↑ 1 2 Darryn Bryant, Peter Danziger. O bipartitních 2-faktorizacích a problému Oberwolfach $K_{n}-I$ // Journal of Graph Theory . - 2011. - T. 68 , č.p. 1 . — S. 22–37 . - doi : 10.1002/jgt.20538 .
↑ Deza A., Franek F., Hua W., Meszka M., Rosa A. Řešení problému Oberwolfach pro objednávky 18 až 40 // Journal of Combinatorial Mathematics and Combinatorial Computing. - 2010. - T. 74 . — S. 95–102 .
↑ Darryn Bryant, Victor Scharaschkin. Kompletní řešení problému Oberwolfach pro nekonečnou sadu objednávek // Journal of Combinatorial Theory . - 2009. - T. 99 , č.p. 6 . — S. 904–918 . - doi : 10.1016/j.jctb.2009.03.003 .
↑ Brian Alspach, Darryn Bryant, Daniel Horsley, Barbara Maenhaut, Victor Scharaschkin. O faktorizaci úplných grafů do oběžných grafů a problému Oberwolfach // Ars Mathematica Contemporanea . - 2016. - T. 11 , no. 1 . — S. 157–173 .
↑ Tommaso Traetta. Kompletní řešení dvoutabulkových problémů Oberwolfachu // Journal of Combinatorial Theory . - 2013. - T. 120 , č.p. 5 . — S. 984–997 . - doi : 10.1016/j.jcta.2013.01.003 .