‘Geachte heer, mevrouw, wij organiseren een running dinner, waarbij deelnemers verschillende gangen op verschillende locaties koken en eten. We zitten al dagen te puzzelen op een schema voor wie wanneer waar eet, zodat iedereen elkaar spreekt. We komen er niet uit, kunt u ons helpen?’ Dat was ongeveer de strekking van een e-mail die binnenkwam bij Platform Wiskunde Nederland, waar ik werk. Ik stuurde hem door, zodat hij tenslotte terecht kwam bij Cor Hurkens van de TU Eindhoven. Die mailde binnen een dag een overzichtelijke tabel met wie wanneer waar moest eten. Het probleem bleek een variant van het zogenaamde Oberwolfach-probleem.

Het Oberwolfach-probleem werd in 1967 geformuleerd tijdens een wiskundeconferentie in het Duitse plaatsje Oberwolfach. Het oorspronkelijke vraagstuk luidt bijna hetzelfde als de vraag uit de e-mail: n deelnemers gaan x verschillende gangen eten op s verschillende locaties. Hoe moeten ze ingedeeld worden zodat iedereen een keer naast elkaar zit? Het verschil tussen de vraagstukken is dat het in het Oberwolfach-probleem niet alleen de bedoeling is met iedereen een keer aan tafel te zitten, maar zelfs iedereen een keer als directe buurman te hebben.

Zo’n probleem kan worden aangepakt met behulp van methodes uit de grafentheorie, een belangrijke tak van de wiskunde. Men geeft dan de situatie weer als een netwerk van punten en lijnen: een graaf. Het uitgangspunt is een graaf met n punten die de verschillende deelnemers voorstellen. Er lopen lijnen van elk punt naar elk ander punt, omdat alle deelnemers elkaar kennen en met elkaar aan tafel geplaatst kunnen worden. U kunt zich misschien al wel voorstellen dat er variaties op het vraagstuk zijn waarbij niet iedereen naast elkaar mag of wil zitten. Een versie is bijvoorbeeld het Emily Post-probleem, waarbij mannen en vrouwen om en om aan tafel geplaatst moeten worden.

Uitgaande van zo’n graaf waarin alle deelnemers worden weergegeven, wordt gezocht naar een opdeling van deze graaf in kleinere grafen, die de tafelschikkingen voorstellen. Elk punt stelt dan opnieuw een deelnemer voor, en een lijn geeft aan dat de deelnemers naast elkaar aan tafel zitten. De kleinere grafen zullen cirkelvormig zijn, omdat elke deelnemer precies één linkerbuur en één rechterbuur heeft. Voor elke gang moet opnieuw zo’n opdeling gemaakt worden, waarbij de moeilijkheid ligt in het aanbrengen van voldoende afwisseling zodat iedereen een keer naast iedereen heeft gezeten.

Nu is het natuurlijk niet zo dat wiskundigen hun tijd doorbrengen met het berekenen van tafelschikkingen voor running dinners, al willen ze wel eens een verzoeknummer doen, zo is gebleken. De vragen die onderzoekers over dit probleem stellen, zijn dieper van aard. Hoeveel gangen moeten er bijvoorbeeld zijn om te zorgen dat n deelnemers ook echt een keer naast ieder ander kunnen zitten? En is er een vaste methode te verzinnen waarmee dit aantal gangen en de bijbehorende tafelschikkingen in elke situatie berekend kan worden?

Wiskundigen gebruiken grafen om allerlei typen netwerken weer te geven, zoals spoorwegnetwerken, telefoonverbindingen en het internet. De huidige dienstregeling van de NS is bijvoorbeeld ontwikkeld door professor Lex Schrijver met behulp van grafentheorie. Dat maakt bovenstaand vraagstuk groter dan alleen de situatie aan de eettafel. Maar onderzoekers houden ook gewoon van een beetje puzzelen, en bedachten al doende allerlei varianten op het Oberwolfach-probleem. Er is bijvoorbeeld ook een ‘echtgenoot-ontwijkende’ variant. Een aantal getrouwde stellen organiseert gezamenlijk verschillende diners, en het is uitdrukkelijk de bedoeling is dat niemand naast de eigen echtgenoot zit.