Alspachs gissning

Alspachs gissning är en matematisk teorem som kännetecknar de osammanhängande cykelomslagen av kompletta grafer med föreskrivna cykellängder. Den är uppkallad efter Brian Alspach , som ställde upp den som ett forskningsproblem 1981. Ett bevis publicerades av Darryn Bryant, Daniel Horsley och William Pettersson ( 2014 ).

Formulering

I det här sammanhanget är ett osammanhängande cykelskydd en uppsättning enkla cykler, varav inte två använder samma kant, som inkluderar alla kanter på en graf. För att ett disjunkt cykelskydd ska existera är det nödvändigt att varje vertex har en jämn grad , eftersom graden av varje vertex är två gånger antalet cykler som inkluderar den vertexen, ett jämnt tal. Och för att cyklerna i ett osammanhängande cykelskydd ska ha en given samling av längder, är det också nödvändigt att summan av de givna cykellängderna är lika med det totala antalet kanter i den givna grafen. Alspach antog att dessa två nödvändiga villkor också är tillräckliga för kompletta grafer: om $n$ är udda (så att graderna är jämna) och en given lista med cykellängder (alla högst $n$ ) lägger till ${\tbinom {n}{2}}$ (antalet kanter i hela grafen) då kan hela grafen $K_{n}$ alltid delas upp i cykler av den angivna längden. Det är detta uttalande som Bryant, Horsley och Pettersson bevisade.

Generalisering till jämna antal hörn

För kompletta grafer $K_{n}$ vars antal $n$ av hörn är jämnt, antog Alspach att det alltid är möjligt att dekomponera grafen till en perfekt matchning och en samling cykler med föreskrivna längder summerande till ${\tbinom {n}{2}}-n/2$ . I detta fall eliminerar matchningen den udda graden vid varje vertex, vilket lämnar en subgraf med jämn grad, och det återstående villkoret är återigen att summan av cykellängderna är lika med antalet kanter som ska täckas. Denna variant av gissningen bevisades också av Bryant, Horsley och Pettersson.

Relaterade problem

Oberwolfach -problemet med dekompositioner av kompletta grafer till kopior av en given 2-regelbunden graf är relaterat, men inget av det är ett specialfall av det andra. Om $G$ är en 2-regelbunden graf, med ${\displaystyle n} hörn, bildad från en disjunkt förening av cykler av vissa längder, då$ skulle en lösning på Oberwolfach-problemet för ${\displaystyle G} också$ ge en uppdelning av hela grafen till $(n-1)/2$ kopior av var och en av cyklerna för $G$ . Men inte varje sönderdelning av $K_{n}$ i så många cykler av varje storlek kan grupperas i osammanhängande cykler som bildar kopior av $G$ , och å andra sidan inte alla instanser av Alspachs gissningar involverar uppsättningar av cykler som har $(n-1)/2$ kopior av varje cykel.

• Alspach, B. (1981), "Problem 3", Research problems, Discrete Mathematics , 36 (3): 333, doi : 10.1016/s0012-365x(81)80029-5
•   Bryant, Darryn; Horsley, Daniel; Pettersson, William (2014), "Cycle decompositions V: Complete graphs into cycles of arbitrary lengths", Proceedings of the London Mathematical Society , Third Series, 108 (5): 1153–1192, arXiv : 1204.3709 , doi ./111 : pl./111 pdt051 , MR 3214677
•   Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2015), "Alspach's conjecture" , Graphs & Digraphs , Textbooks in Mathematics, vol. 39 (6:e upplagan), CRC Press, sid. 349, ISBN 9781498735803