De generatie van snarks

De generatie van snarks
Promotor: Jan Goedgebeur
Snarks zijn 3-reguliere grafen zonder driehoeken die bepaalde sterke connectiviteitsvoorwaarden hebben en waar de bogen niet met 3 kleuren gekleurd kunnen worden. Snarks zijn
interessant omdat voor veel wiskundige vermoedens bewezen kan worden dat ze juist zijn
als en slechts als ze voor snarks juist zijn. Vaak is het zelfs zo dat als er een tegenvoorbeeld
zou zijn, het kleinste tegenvoorbeeld een snark zou zijn. De kleinste snark is de Petersen
graaf (zie figuur hieronder).
Onlangs [1] werd een algoritme ontwikkeld voor de isomorf-vrije generatie van snarks.
Dankzij een programma gebaseerd op dit algoritme was het mogelijk om alle snarks met
hoogstens 36 toppen te bepalen. Op basis van deze nieuwe complete lijsten van snarks
werden reeds 8 gepubliceerde vermoedens ontkracht.
De bedoeling van deze thesis is om een gespecialiseerd algoritme te ontwerpen en te implementeren om veelbelovende deelklassen van snarks te genereren. Meer bepaald: snarks
zonder vier- of vijfhoeken en snarks met sterkere connectiviteitsvoorwaarden dan de algemene snarks. Deze deelklassen van snarks zijn nog interessanter dan de andere snarks
aangezien er voor verschillende vermoedens sterkere voorwaarden voor minimale tegenvoorbeelden bewezen werden. (Bijvoorbeeld dat een minimaal tegenvoorbeeld een snark
zonder vier- of vijfhoeken moet zijn).
Aangezien slechts een beperkt deel van alle snarks tot deze deelklassen behoort, zou een
gespecialiseerde generator voor deze deelklassen van snarks het mogelijk moeten maken om
complete lijsten van deze speciale snarks te genereren met een veel groter aantal toppen
dan wat momenteel mogelijk is. Verder is het ook de bedoeling om verschillende open wiskundige vermoedens te testen op de nieuwe lijsten van snarks die dit programma oplevert.
Meer uitleg kan bekomen worden via: [email protected].
Referenties:
[1] G. Brinkmann, J. Goedgebeur, J. H¨agglund, and K. Markstr¨om. Generation and properties of snarks. Journal of Combinatorial Theory, Series B, 103(4):468–488, 2013.

Download Report