Presentations of independent projects in mathematics

Amanda Borg, Independent projects for mathematics teachers, L1

Date and time: Friday 6/2, 12:00
Place: Cramér meeting room, Albano building 1
Student: Amanda Borg
Supervisor: Per Alexandersson
Title: "Backtracking och n-queens: hur radordning påverkar sökningens effektivitet"

Abstract

"The n-queens problem is well known within the field of combinatorics and has been studied since the mid 19th century. The purpose of the problem is to place n queens on a chessboard of size n x n in such a way that no queens attack each other. Since its beginning, the problem has evolved to also include a three-dimensional point of view. Several real-world applications have been found for the n-queens problem. This essay will cover the problem's historical background and development, mathematical structure, group action in relation to n-queens, and the implication of backtracking to find solutions.

The main focus of this essay is to analyze how the effectiveness of the backtracking algorithm is affected by the order in which the rows of the board are searched. In order to examine this, the 7 x 7 board was searched according to different permutations which represent row orders. To further look at backtracking and its effectiveness, a Python program is used to calculate the maximum number of backtracking steps for n = 4, 5, 6,..., 9. The permutations that resulted in the largest amount of steps are then analyzed and any pattern or structure is noted.

The results of the study show that it is possible to create a permutation from a pre-existing solution and in doing so in a structured manner, one receives a permutation which will generate a new solution with zero backtracking steps needed. By doing this, one will also generate the entire orbit of the original solution. Usage of the Python program showed that there existed both a pattern and structure among the permutations that required the greatest number of backtracking steps. It showed that a permutation had exactly the same amount of backtracking steps as its complement. The results also showed that many of the permutations that were among the least effective ones, began by placing a queen in a corner. By connecting the results to group action the essay demonstrates how group theory can be used to effectively search for solutions to the n-queens problem.

I would like to express my gratitude towards my supervisor Per Alexandersson who has provided me with valuable input during the course of the work. "

Fabian Lukas Grubmüller, Master's thesis, M1

Date and time: Friday 6/2, 13:30
Place: Cramér meeting room, Albano building 1
Student: Fabian Lukas Grubmüller
Supervisor: Anders Mörtberg
Title: "The Category of Iterative Sets in Cubical Agda"

Abstract

"Iterative sets form a constructive Tarski-style universe V⁰ of h-sets. This universe is closed under common type-theoretic constructions and is itself an h-set. It arises naturally from the study of iterative multisets, where V⁰ is defined as a specific type-indexed W-type for which the indexing function is restricted to embeddings, effectively collapsing higher structure.

In previous work, Gratzer, Gylterud, Mörtberg, and Stenholm showed that V⁰ is a model of dependent type theory, in particular a Category with Families (CwF), that admits both Π- and Σ-structures. While their proofs were rather straightforward on paper, often reducing to reflexivity, their formalization in standard Agda (using agda-unimath) faced significant obstacles. For the formalization of Π- and Σ-structures, they faced problems due to complex path algebra involving multiple layers of transport and function extensionality, leading them to abandon the formalization of the Σ-structure.

In this thesis, we explore whether a formalization in Cubical Agda, an extension of Agda for cubical type theory, is easier to accomplish. We implement the general properties of iterative sets, as well as CwF and Σ-structures. For the latter we use three distinct strategies: a naive translation of the prior work, a more cubical approach replacing equalities containing transport with heterogeneous path types, and a strategy that eliminates transport in favor of ad-hoc functions that can be later instantiated by the identity function. We find that while the cubical metatheory simplifies reasoning about extensionality, it also introduces new challenges. One of the main issues is the lack of a definitional J-rule in Cubical Agda, which means that certain terms do not compute definitionally, requiring manual handling of transport structures. Ultimately, we are also unable to finish the proof of the naturality condition for Σ-structures due to the inherent complexity of the goal types. However, our approach substantially simplifies the remaining proof goals, which makes us hopeful that the proof will be able to be completed in future work. We conclude that while Cubical Agda improves clarity in specific areas, we concede that the trade-off regarding the definitional behaviour of the J-rule makes the balance between benefits and downsides approximately equal."

Presentations earlier in the week

There are some more presentations the same week. Abstracts can be found in the calendar article for each day.

Calendar for the Department of Mathematics

Matilda Colarieti Tosti, Bachelor's thesis, K2

Date and time: Monday 2/2, 8:30
Place: Cramér meeting room, Albano building 1
Student: Matilda Colarieti Tosti
Supervisor: Alan Sola
Title: "Convergence of random series"

Carlotta Kvitberg, Independent projects for mathematics teachers

Date and time: Monday 2/2, 9:00
Place: Mittag-Leffler meeting room, Albano building 1
Student: Carlotta Kvitberg
Supervisor: Per Alexandersson
Title: "S-Kalaha: Solving a Swedish variant of Kalaha"

Melvin Segerman, Bachelor's thesis, K1

Date and time: Monday 2/2, 10:30
Place: Mittag-Leffler meeting room, Albano building 1
Student: Melvin Segerman
Supervisor: Yishao Zhou
Title: "Visibility Graphs för tidsserier: Matematiska egenskaper och tillämpningar"

Anders Lindberg, Independent projects for mathematics teachers, L3

Date and time: Monday 2/2, 12:00
Place: Mittag-Leffler meeting room, Albano building 1
Student: Anders Lindberg
Supervisor: Rikard Bögvad
Title: "Transcendenta tal"

Niklas Hellberg, Independent projects for mathematics teachers, L4

Date and time: Monday 2/2, 12:00
Place: Cramér meeting room, Albano building 1
Student: Niklas Hellberg
Supervisor: Boris Shapiro
Title: "Finite Fields: An Introduction"

Felix Nordgren Odhner, Independent projects for mathematics teachers, L5

Date and time: Tuesday 3/2, 10:00
Place: Meeting room 25, Albano building 2
Student: Felix Nordgren Odhner
Supervisor: Sofia Tirabassi
Title: "Polynomials of Degree 3 and 4: Classical Solution Methods and Their Significance"

Jessica Ramström, Independent projects for mathematics teachers, L6

Date and time: Thursday 5/2, 8:00
Place: Meeting room 25, Albano building 2
Student: Jessica Ramström
Supervisor: Pavel Kurasov
Title: "Sturm-Liouville theory"

Gülhan Sariismailoglu, Bachelor's thesis, K3

Date and time: Thursday 5/2, 14:00
Place: Meeting room 9, Albano building 1
Student: Gülhan Sariismailoglu
Supervisor: Gregory Arone
Title: "Picks sats"