Tournament Schedules Using Combinatorial Design Theory
Translated title
Turneringsplanlægning ved brug af designteori
Author
Thorsen, Christian Serup Ravn
Term
4. term
Education
Publication year
2021
Submitted on
2021-01-08
Pages
42
Abstract
Denne afhandling undersøger, hvordan man kan planlægge turneringer med visse symmetrikrav ud fra et kombinatorisk perspektiv. Den introducerer blokdesigns—matematiske skabeloner til at arrangere elementer i grupper, så par optræder i et kontrolleret mønster—og gennemgår centrale egenskaber og resultater. Særligt bruges Fishers ulighed og Bruck-Ryser-Chowla-sætningen til at udelukke, at bestemte design kan eksistere: Fishers ulighed gælder for alle design, mens Bruck-Ryser-Chowla-sætningen gælder for symmetriske design. Med dette udgangspunkt konstruerer afhandlingen spilleplaner for en enkel alle-mod-alle-turnering med 2n hold (hvert holdpar mødes én gang). Den bruger opløselige design og differenssystemer til at fordele kampe og hjemme/ude-baner. I den første konstruktion fås 2n−2 brud i hjemme/ude-mønsteret, hvor et “brud” betyder, at et hold spiller to hjemmekampe eller to udekampe i træk. Dette udvides dernæst til en fuld anden halvdel med byttede spillesteder. Den resulterende plan har 6n−6 brud og ingen på hinanden følgende brud, dvs. brud optræder ikke lige efter hinanden for noget hold. Afhandlingen beskriver også en fejl i den oprindelige konstruktion og giver en rettelse. Den korrigerede plan undgår situationen, hvor to hold x og y begge møder hold z umiddelbart efter at have spillet mod hold w.
This thesis studies how to set up tournament schedules with certain symmetry requirements using tools from combinatorics. It introduces block designs—mathematical templates for grouping elements so that pairs occur in a controlled pattern—and reviews key properties and results. In particular, Fisher’s inequality and the Bruck-Ryser-Chowla theorem are used to rule out the existence of some designs: Fisher’s inequality applies to any design, while the Bruck-Ryser-Chowla theorem applies to symmetric designs. Using this framework, the thesis builds schedules for a single round-robin tournament with 2n teams (each pair meets once). It uses resolvable designs and difference systems to assign matches and home/away venues. In the first construction, there are 2n−2 breaks in the home–away pattern, where a “break” means a team plays two consecutive home games or two consecutive away games. This is then extended to a full second half by swapping venues. The resulting schedule has 6n−6 breaks and no consecutive breaks, meaning breaks do not occur back-to-back for any team. The thesis also identifies a flaw in the initial construction and provides a fix. The corrected schedule avoids the situation where two teams x and y both face team z immediately after playing team w.
[This abstract was generated with the help of AI]
Keywords
Documents