Oberwolfachův problém - Oberwolfach problem

Nevyřešený problém v matematice: Pro které 2-pravidelné ${ displaystyle n}$-vertexové grafy ${ displaystyle G}$ může celý graf ${ displaystyle K_ {n}}$ být rozloženy na okrajově disjunktní kopie ${ displaystyle G}$? (více nevyřešených úloh z matematiky)

Rozklad celého grafu ${ displaystyle K_ {7}}$ do tří kopií ${ displaystyle C_ {3} + C_ {4}}$, řešení problému Oberwolfach pro vstup ${ displaystyle (3,4)}$

The Oberwolfachův problém je nevyřešený problém v matematice, který může být formulován buď jako problém plánování úkolů sezení pro hosty, nebo abstraktněji jako problém v teorie grafů, na kryty okrajových cyklů z kompletní grafy. Je pojmenována po Mathematical Research Institute of Oberwolfach, kde problém nastolil v roce 1967 Gerhard Ringel.^[1]

Formulace

Na konferencích konaných v Oberwolfachu je zvykem, že účastníci večeří společně v místnosti s kruhovými stoly, které nemají stejnou velikost a mají přiřazené posezení, které účastníky přeskupuje od jídla k jídlu. Problém Oberwolfach se ptá, jak vytvořit tabulku sezení pro danou sadu stolů tak, aby byly všechny stoly u každého jídla plné a všechny páry účastníků konference byly posazeny vedle sebe přesně jednou. Instanci problému lze označit jako ${ displaystyle OP (x, y, z, tečky)}$ kde ${ displaystyle x, y, z, tečky}$ jsou dané velikosti tabulky. Alternativně, když se některé velikosti tabulky opakují, mohou být označeny pomocí exponenciální notace; například, ${ displaystyle OP (5 ^ {3})}$ popisuje instanci se třemi tabulkami velikosti pět.^[1]

Formulováno jako problém v teorii grafů, dvojice lidí, kteří sedí vedle sebe při jednom jídle, mohou být reprezentovány jako disjunktní unie z cyklické grafy ${ displaystyle C_ {x} + C_ {y} + C_ {z} + cdots}$ specifikovaných délek, s jedním cyklem pro každý z jídelních stolů. Toto spojení cyklů je a 2-pravidelný graf a každý 2 pravidelný graf má tento tvar. Li ${ displaystyle G}$ je tento 2-pravidelný graf a má ${ displaystyle n}$ vrcholy, otázkou je, zda celý graf ${ displaystyle K_ {n}}$ může být reprezentován jako okrajově disjunktní sjednocení kopií ${ displaystyle G}$.^[1]

Aby řešení mohlo existovat, musí být celkový počet účastníků konference (nebo ekvivalentně celková kapacita tabulek nebo celkový počet vrcholů grafů daného cyklu) lichý. U každého jídla sedí každý účastník vedle dvou sousedů, takže celkový počet sousedů každého účastníka musí být sudý, a to je možné pouze tehdy, když je celkový počet účastníků lichý. Problém byl však také rozšířen na sudé hodnoty ${ displaystyle n}$ tím, že o ně žádáte ${ displaystyle n}$, zda všechny okraje celého grafu kromě a perfektní shoda lze zakrýt kopiemi daného 2 pravidelného grafu. Jako problém ménage (jiný matematický problém zahrnující uspořádání sezení stolů a stolů), lze tuto variantu problému formulovat za předpokladu, že ${ displaystyle n}$ večeře jsou uspořádány do ${ displaystyle n / 2}$ manželské páry a že uspořádání sezení by mělo umístit každého hosta vedle sebe, kromě jejich vlastního manžela právě jednou.^[2]

Známé výsledky

Jediné případy Oberwolfachova problému, o nichž je známo, že jsou neřešitelné, jsou ${ displaystyle OP (3 ^ {2})}$, ${ displaystyle OP (3 ^ {4})}$, ${ displaystyle OP (4,5)}$, a ${ displaystyle OP (3,3,5)}$^[3]. Všeobecně se věří, že všechny ostatní případy mají řešení, ale pouze zvláštní případy se ukázaly být řešitelnými.

Mezi případy, pro které je řešení známé, patří:

• Všechny instance ${ displaystyle OP (x ^ {y})}$ až na ${ displaystyle OP (3 ^ {2})}$ a ${ displaystyle OP (3 ^ {4})}$.^{[4][5][6][7][2]}
• Všechny instance, ve kterých mají všechny cykly sudou délku.^[4][8]
• Všechny instance (jiné než známé výjimky) s ${ Displaystyle n leq 60}$.^[9][3]
• Všechny instance pro určité možnosti ${ displaystyle n}$, patřící do nekonečných podmnožin přirozených čísel.^[10][11]
• Všechny instance ${ displaystyle OP (x, y)}$ jiné než známé výjimky ${ displaystyle OP (3,3)}$ a ${ displaystyle OP (4,5)}$.^[12]

Související problémy

Kirkmanova školačka problém, seskupení patnácti školaček do řad po třech sedmi různými způsoby, aby se každá dvojice dívek objevila jednou v každé trojici, je zvláštním případem problému Oberwolfach, ${ displaystyle OP (3 ^ {5})}$. Problém Hamiltoniánský rozklad úplného grafu ${ displaystyle K_ {n}}$ je další speciální případ, ${ displaystyle OP (n)}$.^[8]

Alspachova domněnka, o rozkladu celého grafu na cykly daných velikostí, souvisí s Oberwolfachovým problémem, ale ani jeden z nich není zvláštním případem druhého. ${ displaystyle G}$ je 2 pravidelný graf s ${ displaystyle n}$ vrcholy, vytvořené z disjunktního spojení cyklů určitých délek, pak řešení Oberwolfachova problému pro ${ displaystyle G}$ by také poskytlo rozklad celého grafu na ${ displaystyle (n-1) / 2}$ kopie každého z cyklů ${ displaystyle G}$. Nicméně, ne každý rozklad ${ displaystyle K_ {n}}$ do těchto mnoha cyklů každé velikosti lze seskupit do disjunktních cyklů, které tvoří kopie ${ displaystyle G}$a na druhé straně ne každá instance Alspachova domněnky zahrnuje sady cyklů, které mají ${ displaystyle (n-1) / 2}$ kopie každého cyklu.

Reference