Problema Oberwolfach

Probleme nerezolvate la matematică : Pentru orice graf cu 2 vârfuri regulate , graficul complet poate fi descompus în copii disjunse de muchii ale graficului ?

G

n

K_n

G

Problema Oberwolfach este o problemă matematică nerezolvată care poate fi formulată ca o problemă de alocare a locurilor pentru cine sau, mai abstract, ca o problemă de teoria grafurilor despre acoperirea graficelor complete prin cicluri de muchii . Problema a fost numită după Institutul de Matematică Oberwolfach , unde problema a fost formulată în 1967 de Gerhard Ringel [1] .

Formulare

La conferințele desfășurate la Oberwolfach se obișnuiește să luăm masa împreună într-o sală cu mese rotunde, care nu sunt toate de aceeași dimensiune, iar locurile la mese se schimbă de la prânz la cină. Problema Oberwolfach întreabă cum se specifică distribuția locurilor la mese, astfel încât toate locurile să fie ocupate și toate perechile de participanți la conferință să stea unul lângă altul o singură dată. Instanța sarcinii poate fi desemnată ca , unde specifică dimensiunile tabelelor. Alternativ, atunci când unele dimensiuni de mese sunt repetate, acest lucru poate fi reflectat ca un superscript, cum ar fi descrierea unei probleme cu trei mese pentru cinci locuri [1] . $OP(x,y,z,\dots )$ $x,y,z,\dots$ $OP(5^{3})$

Când problema este formulată ca o problemă de teorie a grafurilor, perechile de oameni care stau unul lângă altul la o anumită cină pot fi reprezentate ca o uniune de cicluri neintersectate (de-a lungul marginilor) de o anumită lungime, câte un ciclu pentru fiecare. masa. Această uniune de cicluri este un graf cu 2 regulate și orice graf cu 2 regulate are această formă. Dacă este un astfel de graf 2-regular și are vârfuri, întrebarea se pune după cum urmează: poate fi reprezentat graficul complet ca o uniune de copii ale grafului care nu se intersectează de-a lungul muchiilor [1] . $C_{x}+C_{y}+C_{z}+\cdots$ $G$ $n$ $K_n$ $G$

Pentru ca o soluție să existe, numărul total de participanți la conferință (sau, echivalent, numărul total de locuri la mese, sau numărul total de vârfuri ale ciclurilor date) trebuie să fie un număr impar. La fiecare cină, participantul se așează lângă alți doi participanți, astfel încât numărul total de vecini ai fiecărui participant trebuie să fie par, iar acest lucru este posibil doar dacă numărul total de participanți este impar. Problema, totuși, poate fi extinsă la valori egale ale , dacă se solicită acestea , dacă este posibil să se acopere toate marginile graficului complet, cu excepția unei potriviri perfecte, cu copii ale unui grafic 2-regular dat. Ca și problema cuplurilor (o altă problemă de matematică despre așezarea la masă), această variantă a problemei poate fi formulată presupunând că participanții la cină sunt împărțiți în cupluri căsătorite și că fiecare participant trebuie să ia masa exact o dată cu fiecare alt participant, cu excepția soțului (soțului) [2] . $n$ $n$ $n$ $n/2$

Rezultate notabile

Sunt cunoscute doar următoarele cazuri ale problemei Oberwolfach despre care se știe că nu au nicio soluție: , , și . Se crede pe scară largă că toate celelalte instanțe ale soluției au, dar până acum doar cazurile speciale s-au dovedit rezolvabile. $OP(3^{2})$ $OP(3^{4})$ $OP(4,5)$ $OP(3,3,5)$

Cazuri pentru care se cunosc soluții:

Toate instanțele, cu excepția și [3] [4] [5] [6] [2] . $OP(x^{y})$ $OP(3^{2})$ $OP(3^{4})$
Toate cazurile în care toate ciclurile sunt de lungime uniformă [3] [7] .
Toate instanțele (cu excepția excepțiilor cunoscute) de la [8] . $n\leqslant 40$
Toate instanțele pentru unele aparținând unui set infinit de numere prime [9] [10] . $n$
Toate instanțele, cu excepția excepțiilor cunoscute și [11] . $OP(x,y)$ $OP(3,3)$ $OP(4,5)$

Sarcini conexe

Problema elevelor lui Kirkman : Gruparea a cincisprezece eleve în rânduri de trei în șapte moduri diferite, astfel încât fiecare pereche de fete să fie în primele trei o singură dată, este un caz special al problemei Oberwolfach . Problema descompunerii hamiltoniene a unui graf complet este un alt caz special [7] . $OP(3^{5})$ $K_n$ $OP(n)$

Conjectura lui Alspach despre descompunerea unui grafic complet în cicluri de dimensiuni date este legată de problema Oberwolfach, dar nu sunt cazuri speciale unul de altul. Dacă este un grafic 2-regulat cu vârfuri formate din cicluri neintersectate de o anumită lungime, atunci soluția problemei Oberwolfach pentru oferă o descompunere a graficului complet în copii ale fiecărui ciclu al graficului . Cu toate acestea, nu orice descompunere în atât de multe cicluri de fiecare dimensiune poate fi grupată în cicluri disjunse care formează copii ale lui , dar, pe de altă parte, nu fiecare instanță a conjecturii lui Alspach implică un set de cicluri care au copii ale fiecărui ciclu. $G$ $n$ $G$ $(n-1)/2$ $G$ $K_n$ $G$ $(n-1)/2$

Note

↑ 1 2 3 Hanfried Lenz, Gerhard Ringel . O scurtă trecere în revistă a lucrării matematice a lui Egmont Köhler // Matematică discretă . - 1991. - T. 97 , nr. 1-3 . — S. 3–16 . - doi : 10.1016/0012-365X(91)90416-Y .
↑ 1 2 Charlotte Huang, Anton Kotzig, Alexander Rosa. Pe o variantă a problemei Oberwolfach // Matematică discretă. - 1979. - T. 27 , nr. 3 . — S. 261–277 . - doi : 10.1016/0012-365X(79)90162-6 .
↑ 1 2 Roland Häggkvist. O lemă privind descompunerea ciclului // Cicluri în grafice (Burnaby, BC, 1982). - Olanda de Nord, 1985. - T. 115. - S. 227-232. - (North-Holland Math. Stud.). - doi : 10.1016/S0304-0208(08)73015-9 .
↑ Brian Alspach, Roland Häggkvist. Câteva observații asupra problemei Oberwolfach // Journal of Graph Theory . - 1985. - T. 9 , nr. 1 . — S. 177–187 . - doi : 10.1002/jgt.3190090114 .
↑ Brian Alspach, Schellenberg PJ, Stinson DR, David Wagner. Problema Oberwolfach și factorii ciclurilor de lungime impară uniforme // Journal of Combinatorial Theory . - 1989. - T. 52 , nr. 1 . — S. 20–43 . - doi : 10.1016/0097-3165(89)90059-9 .
↑ Hoffman DG, Schellenberg PJ The exist of -factorizations of // Discrete Mathematics . - 1991. - T. 97 , nr. 1-3 . — S. 243–250 . - doi : 10.1016/0012-365X(91)90440-D . $C_{k}$ $K_{2n}-F$
↑ 1 2 Darryn Bryant, Peter Danziger. Despre 2-factorizări bipartite ale și problema Oberwolfach $K_{n}-I$ // Journal of Graph Theory . - 2011. - T. 68 , nr. 1 . — S. 22–37 . - doi : 10.1002/jgt.20538 .
↑ Deza A., Franek F., Hua W., Meszka M., Rosa A. Solutions to the Oberwolfach problem for orders 18 to 40 // Journal of Combinatorial Mathematics and Combinatorial Computing. - 2010. - T. 74 . — S. 95–102 .
↑ Darryn Bryant, Victor Scharaschkin. Soluții complete la problema Oberwolfach pentru un set infinit de ordine // Journal of Combinatorial Theory . - 2009. - T. 99 , nr. 6 . — S. 904–918 . - doi : 10.1016/j.jctb.2009.03.003 .
↑ Brian Alspach, Darryn Bryant, Daniel Horsley, Barbara Maenhaut, Victor Scharaschkin. Despre factorizările grafurilor complete în grafuri circulante și problema Oberwolfach // Ars Mathematica Contemporanea . - 2016. - T. 11 , nr. 1 . — S. 157–173 .
↑ Tommaso Traetta. O soluție completă la problemele Oberwolfach cu două tabele // Journal of Combinatorial Theory . - 2013. - T. 120 , nr. 5 . — S. 984–997 . - doi : 10.1016/j.jcta.2013.01.003 .