Fair Tournament Design
2025 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE credits
Student thesis
Abstract [en]
This thesis investigates a problem in combinatorial design theory, constructing fair tournament schedules according to a set of combinatorial constraints. We model tournaments with incidence matrices, and given different parameters we aim to characterize the solution set, all incidence matrices that satisfy the given constraints. Permuting the rows and columns of a matrix in the solution set results in a new solution. Since permuted matrices have essentially the same structure, we define these to be isomorphic. Therefore, we focus on classifying the solution set into isomorphism classes, which provide a more insightful representation.
Our analysis establishes some necessary conditions on solutions and characterizes a few solution sets. We find multiple equivalent problem formulations and identify connections to different mathematical fields.
Through the use of singular value decomposition we show that all solutions are in the same orbit under right multiplication by an orthogonal matrix. Also, all binary matrices in this orbit are solutions, and another matrix in the same orbit can be found trivially. This allows us to reframe the problem to finding all orthogonal matrices that yield binary matrices.
A key insight is that some cases reduce to the problem of finite projective planes, from which many important results follow. For example, for some choices of parameters there are in fact solutions in different isomorphism classes - solutions with fundamentally different structure.
Place, publisher, year, edition, pages
2025.
Series
TRITA-SCI-GRU ; 2025:339
Keywords [en]
mathematics, combinatorics, design, algebra, projective planes
National Category
Mathematical sciences
Identifiers
URN: urn:nbn:se:kth:diva-368324OAI: oai:DiVA.org:kth-368324DiVA, id: diva2:1988505
Subject / course
Mathematics
Educational program
Master of Science in Engineering - Engineering Mathematics
Supervisors
Examiners
2025-08-122025-08-122025-08-12Bibliographically approved