Master's Project in Combinatorics
(Examensarbete i kombinatorik)

On this page you can find information about writing a master's thesis (examensarbete) in combinatorics. Examples of both new topics and finished projects are listed below, but we have more of them. Do not hesitate to contact anyone in the Combinatorics Group to discuss thesis topics.

Examples of topics

Restricted Lattice Paths

The theory of lattice paths is full of interesting and important results.

If we for instance allow steps to the right (1,0) and up (0,1) and restrict to paths staying below the line x=y, then the number of such paths starting in the origin and ending in (n,n) is counted by the n:th Catalan number. If we also allow diagonal steps (1,1) then the number of paths is the Schröder number. There are also interesting lattice path theorems when we want to have several non-intersecting lattice paths at the same time in the lattice. The interest in lattice paths often come from other problems that can be reformulated to questions about lattice paths. But the lattice paths are also very interesting in their own right.

In a recent master's thesis (examensarbete) Robert Johansson was able to enumerate a special class of so called alternating sign matrices which also resulted in a bijection to the Schröder paths defined above. This resulted in a published research paper. Inspired by this work I suggest a new study of Schröder and Catalan paths with some restrictions which could be very fruitful.

Goal

The goal is to find and prove new results on the number of lattice paths with certain restrictions.

Prerequisites

SF2708 Combinatorics, or knowledge of similar level.

Contact person

Svante Linusson, 08-7909444, linusson@math.kth.se

Combinatorics of Simplicial Complexes

A finite simplicial complex is a family Δ of subsets of a finite set X such that if a set σ belongs to Δ, then every subset of σ also belongs to Δ. Members of Δ are called faces. An important special case is that all faces have size at most two. In that case, we may view Δ as an ordinary graph with vertex set X. Namely, we may interpret a given face {x,y} of size two as an edge joining the two vertices x and y. Larger faces also admit geometric interpretations. For example, we may view a face {x,y,z} of size three as a filled triangle with corners x, y, and z, whereas a face of size four corresponds to a three-dimensional tetrahedron with four corners.

An important parameter associated to a simplicial complex Δ is the Euler characteristic χ_Δ, which is an alternating sum over all faces of Δ. Specifically, we add one for each set of odd size and subtract one for each set of even size. For example, if the complex is a graph G in the sense described above with e edges (faces of size two) and v vertices (faces of size one), then χ_G = -e+v-1. If G is a connected planar graph, then χ_G is equal to minus the number of bounded regions when G is drawn in the plane without crossing edges. Similar characterizations of the Euler characteristic also exist for more general classes of simplicial complexes.

One possible direction of the project would be to analyze the Euler characteristic of various classes of simplicial complexes. For example, one might study operations on complexes that either preserve the Euler characteristic or change the sign. For example, given any complex Δ, we may introduce two new vertices x and y and define Σ = {σ, σ ∪ {x}, σ ∪ {y} : σ belongs to Δ}. Then χ_Σ = - χ_Δ. A possible goal of the project would be to find other, more intricate, constructions with similar properties. (This is just an example of what the project might look like.)

The student may choose between different approaches. A more combinatorial approach would be roughly as described above with the focus being on Euler characteristic. A more algebraic approach would be to focus on simplicial homology, a concept closely related to Euler characteristic that generalizes the notion of bounded regions of a connected planar graph. Vaguely speaking, the homology of a simplicial complex is a linear-algebraic measure on the amount of "holes" of various dimensions in the complex, when viewed as a geometric object. Whatever approach chosen, learning the basics of simplicial homology will be part of the project.

Goal

The goal is to prove results about the Euler characteristic and/or the homology of various classes of simplicial complexes.

Prerequisites

Linear algebra and a second course in combinatorics or discrete mathematics is desirable.

Contact person

Jakob Jonsson, 08-7907202, jakobj@math.kth.se

Finished projects

On the Bunkbed Conjecture

Madeleine Leander (Stockholm University)

June 2009

Advisor: Svante Linusson

Abstract. Let G be a finite graph and consider the bunkbed graph G* = G x K₂ where K₂ is the graph consisting of two vertices, {0,1} and one edge connecting them. On G* consider the percolation model with p the probability that an edge e exists, for all e in G. All edges will exist or not independently of each other. We write u ↔ v for the event "there is a path from u to v". The bunkbed conjecture states that for any bunkbed graph G* = G x K₂, corresponding to a finite graph G the following holds

for all u, v in V(G) and any probability p. The bunkbed conjecture was first informally stated by P. W. Kasteleyn around 1985 and has influenced the research of mathematicians like van den Berg, Kahn, Häggstrom and Linusson since. The main purpose of this thesis is to use combinatorial tools to work on the bunkbed conjecture. The bunkbed conjecture will be proven to be true for wheels and some small graphs.

Download the thesis

Representing Matroids By Polynomials with the Half-Plane Property

Rafael S. González D'León

May 2009

Advisor: Petter Brändén

Algebraic Statistics: Graph Homomorphism Ideals

Patrik Norén

May 2009

Advisor: Alexander Engström

Optimal Strategy in the Children's Game Memory

Erik Alfthan

May 2007

Advisor: Svante Linusson

Abstract. Two mathematical games are contructed from the children's game memory. One game, named Terminating memory is constructed as a two player game with rules as close to the children's game as possible. The most significant change is made in order to make the game terminate. It turns out that there are non-trivial elements of strategy in Terminating memory. Depending on the expected number of turn overs, i.e. the number of times the lead is lost, the strategy seems to be to try to force the opponent to reach a known losing position which is when the last turn over occurs. However, this could not be proven generally, but is computed for all games with less than 200 pairs. A second game of memory that complies with the rules of combinatorial games was therefore contructed, in order to determine which elements are important to the previous game, Terminating memory. This game, Combinatorial memory was generally solved as game equivalent to a sequence of weighted misere nim games. A hypothesis of implications of this to Terminating memory was presented. It is suggested that the strategy will depend on whether there are expected to be odd or even number of nim games left, of which the last game is probably the largest. Both player are trying to reach a position where they will get the last collect sequence. This is consistant with the main conjecture of terminating memory. A general way to compute whether odd or even number of remaining nim games is most likely is needed to make this result useful.

Download the thesis

The Bruhat Order on Involutions and Pattern Avoidance

Kathrin Vorwerk

April 2007

Advisors: Christoph Helmberg (TU Chemnitz) och Axel Hultman

Abstract. The symmetric group, the group of signed permutations and the group of signed permutations with even number of negative entries are Coxeter groups and can be seen as partially ordered sets with respect to the Bruhat order. A result of Tenner (2006) shows that the elements of those posets which have a boolean lower order ideal are exactly those avoiding certain sets of patterns. The theory of twisted involutions was developed by Richardson and Springer (1990) and Hultman (2004). We show that a twisted involution having a boolean lower order ideal can be characterized in terms of reduced twisted expressions. We also consider the special case of involutions of the groups mentioned above and show that those are again characterized by the avoidance of certain sets of patterns. We enumerate the boolean involutions of the said groups recursively. For the involutions of the symmetric group we can also give recursions with respect to some well-known statistics and a bijection with a certain class of Motzkin paths.

Download the thesis

Tight Span Used in Phylogenetics

Pio Korinth

April 2007

Advisor: Svante Linusson

Abstract. Suppose we have a set of species and that we know the genetic difference between any pair in that set. We want to figure out which species have the same ancestor/ancestors. One way of finding approximative solutions is using a mathematical tool known as Tight Span. I will describe what Tight Span is and also implement my own algorithm using Tight Span on computers. I will also describe a way to show how a conjecture given by Andreas W.M. Dress in [1] on pages 342-345 can be deduced from a different conjecture I have formulated as well as describing another method I have developed for construction of phylogenetic trees. This last method does not use Tight Span and has not yet been implemented.

[1] A. W. M. Dress, Trees, Tight Extensions of Metric Spaces, and the Cohomological Dimension of Certain Groups: A Note on Combinatorial Properties of Metric Spaces, Advances in Mathematics 53 (1984), no. 4, 321--402.

Download the thesis

Maximal partial packings of Z₂ⁿ with perfect codes

Thomas Westerbäck

December 2005

Advisor: Olof Heden

A revised version is published here:
Designs, Codes and Cryptography 42 (2007), No. 3, 335-355.

Abstract. A maximal partial Hamming packing of Z₂ⁿ is defined by us to be a family S of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in S. The number of translates of Hamming codes in S is the packing number, and a partial Hamming packing is strictly partial if the family S does not constitute a partition of Z₂ⁿ.

A simple and useful condition describing when two translates of Hamming codes are disjunct or not disjunct is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of Z₂ⁿ, n = 2^m - 1, satisfies m + 1 ≤ p ≤ n - 1.

It is also proved that for any n equal to 2^m -1, m ≥ 4, there exist maximal strictly partial Hamming packings of Z₂ⁿ with packing numbers n - 10, n - 9, n - 8, ... , n - 1. This implies that the upper bound is tight for any n = 2^m - 1, m ≥ 4.

All packing numbers for maximal strictly partial Hamming packings of Z₂ⁿ, n = 7 and 15, are given by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5, 6, 7, ... , 13 and 14.

Download the thesis