In this thesis, we will define the topswop forest and study the properties of the forest. We will show the number of trees and leaves in the forest. We will also do an experiment to show there is more than an exponential growth between the number of nodes of each tree and the number of elements in the permutation. The experiment also shows that the tallest tree doesn’t always contain the identity permutation. In the later section, we derive a linear lower bound for the topswop problem by studying a specific family of permutation.

A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. Furthermore, we show properties of edge cuts and particular graphs which are no induced subgraphs. We demonstrate that there are infinitely many minimal non-(2, 1)-colorable graphs, at least one of order n for all n ≥ 5. Moreover, we present all minimal non-(2, 1)- colorable graphs of order at most seven. We consider the maximum degree of minimal non-(2, 1)-colorable graphs and show that it is at least four but can be arbitrarily large. We prove that the average degree is greater than 8/3 and give sufficient properties for graphs with average degree greater than 14/5. We conjecture that all minimal non-(2, 1)-colorable graphs fulfill these properties.

In the mid 1900s the area of extremal graph theory took its first propersteps with the proof of Turán’s theorem. In 1963 Pál Erdős asked for an extension of this fundamental result regarding (n, s, q)-graphs; graphs on n vertices in which any s-set of vertices spans at most q edges, and multiple edges are allowed; and raised the question of determining ex(n, s, q), the maximum number of edges spanning such a graph. More recently, Mubayi and Terry looked at the problem of determining the maximum productof the edges in (n, s, q)-graphs. Their proof was further investigated by Day, Falgas-Ravry and Treglown who, in particular, settled a conjecture of Mubayi and Terry regarding the case (s, q) = (4, 6a+3), for a ∈ Z≥2. In this thesis we look at the case (s, q) = (5, 24), which is mentioned as an open problem at the end of the paper by Day, Falgas-Ravry and Treglown. A hypothetical extremal construction was provided by Victor Falgas-Ravry, and we prove it to be asymptotically optimal.

The hypercube Qn is the graph whose vertices are the ordered n-tuples of zeros and ones, where two vertices are adjacent iff they differ in exactly one coordinate. A partial edge coloring f of a graph G is a mapping from a subset of edges of G to a set of colors; it is called proper if no pair of adjacent edges share the same color. A (possibly partial and unproper) coloring f is avoidable if there exists a proper coloring g such that no edge has the same color under f and g. An unavoidable coloring h is called minimal if it would be avoidable by letting any colored edge turn noncolored. We construct a computer program to find all minimal unavoidable edge colorings of Q3 using up to 3 colors, and draw some conclusions for general Qn.

This thesis consists of the four papers listed below and a survey of the research area. I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k II Lina J. Andrén: Avoidability of random arrays III Lina J. Andr´en: Avoidability by Latin squares of arrays with even order IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares Papers I, III and IV are all concerned with a conjecture by Häggkvist saying that there is a constant c such that for any positive integer n, if m ≤ cn, then for every n × n array A of subsets of {1, . . . , n} such that no cell contains a set of size greater than m, and none of the elements 1, . . . , n belongs to more than m of the sets in any row or any column of A, there is a Latin square L on the symbols 1, . . . , n such that there is no cell in L that contains a symbol that belongs to the set in the corresponding cell of A. Such a Latin square is said to avoid A. In Paper I, the conjecture is proved in the special case of order n = 2k . Paper III improves on the techniques of Paper I, expanding the proof to cover all arrays of even order. Finally, in Paper IV, similar methods are used together with a recoloring theorem to prove the conjecture for all orders. Paper II considers another aspect of the problem by asking to what extent way a deterministic result concerning the existence of Latin squares that avoid certain arrays can be used when the sets in the array are assigned randomly. / Denna avhandling inehåller de fyra nedan uppräknade artiklarna, samt en översikt av forskningsområdet. I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k II Lina J. Andrén: Avoidability of random arrays III Lina J. Andrén: Avoidability by Latin squares of arrays with even order IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares Artikel I, III och IV behandlar en förmodan av Häggkvist, som säger att det finns en konstant c sådan att för varje positivt heltal n gäller att om m ≤ cn så finns för varje n × n array A av delmängder till {1, . . . ,n} sådan att ingen cell i A i innehåller fler än m symboler, och ingen symbol förekommer i fler än m celler i någon av raderna eller kolumnerna, så finns en latinsk kvadrat L sådan att ingen cell i L innehåller en symbol som förekommer i motsvarande cell i A. En sådan latinsk kvadrat sägs undvika A. Artikel I innehåller ett bevis av förmodan i specialfallet n = 2k. Artikel III använder och utökar metoderna i Artikel I till ett bevis av förmodan för alla latinska kvadrater av jämn ordning. Förmodan visas slutligen för samtliga ordningar i Artikel IV, där bevismetoden liknar den som finns i i Artikel I och III tillsammans med en omfärgningssats. Artikel II behandlar en annan aspekt av problemet genom att undersöka vad ett deterministiskt resultat om existens av latinska kvadrater som undviker en viss typ av array säger om arrayer där mängderna tilldelas slumpmässigt.

Syftet med denna kvalitativa studie är att beskriva variationen av strategier som elever använder sig av vid behandling av diskreta mängder inom tal i bråkform, då uppgifterna är av varierad art och där objekten är ordnade såväl som oordnade. För att erhålla ett brett underlag genomfördes uppgiftsdiagnoser, på 78 elever i årskurs sex, vilka utifrån elevernas svar och anteckningar analyserades för att identifiera förekommande strategier. Analysen resulterade i elva skilda strategier inom fyra övergripande kategorier: heltalstillämpning av tal i bråkform, formation av helhet, formation av enhet och operation på och med tal i bråkform. De ingående strategierna i kategorin heltalstillämpning av tal i bråkform nyttjar bråkuttryck som heltal på så vis att de ingående talen antingen utgör ett antal objekt eller ses som föremål för en operation. Inom formation av helhet ingår strategier inom vilka eleverna på olika sätt delar upp helheten utifrån nämnarens storlek medan strategierna inom formation av enhet har det gemensamt att eleverna utifrån sin förförståelse grupperar de ingående objekten i enheter. I vissa fall samlar eleverna objekten i större grupper medan elever i andra fall ser till varje enskilt objekt. Slutligen innefattar kategorin operation på och med tal i bråkform strategier som använder sig av aritmetiska resonemang. Utmärkande för  och centralt i de identifierade strategierna är genomgående förståelsen för bråkbegreppets innebörd. Utifrån kunskap om den variation av strategier som elever använder hoppas vi att lärare kan få en större förståelse för de resonemang som elever för och att undervisningen därigenom utformas för att möta alla elevers individuella förutsättningar och behov av stöd.

In this paper, new variations of some well-known permutation statistics are introduced and studied. Firstly, a double-descent of a permutation π is defined as a position i where πi ≥ 2πi+1. By proofs by induction and direct proofs, recursive and explicit expressions for the number of n-permutations with k double-descents are presented. Also, an expression for the total number of double-descents in all n-permutations is presented. Secondly, a double-inversion of a permutation π is defined as a pair (πi,πj) where i<j but πi ≥ 2πj. The total number of double-inversions in all n-permutations is presented.

In 2004 Alexander Postnikov and Boris Shapiro introduced a class of commutative algebras for non-directed graphs. There are two main types of such algebras, algebras of the first type count spanning trees and algebras  of the second type count spanning forests. These algebras have a number of interesting properties including an explicit formula for their Hilbert series. In this thesis we mainly work with the second type of algebras, we discover more properties of the original algebra and construct a few generalizations. In particular we prove that the algebra counting forests depends only on graphical matroid of the graph and converse. Furthermore, its "K-theoretic" filtration reconstructs the whole graph. We introduse $t$ labelled algebras of a graph, their Hilbert series contains complete information about the Tutte polynomial of the initial graph. Finally we introduce similar algebras for hypergraphs. To do this, we define spanning forests and trees of a hypergraph and the corresponding "hypergraphical" matroid.

The set PLS(a, b; n) is the set of all partial latin squares of order n with a completed rows, b completed columns and all other cells empty. We identify reductions of partial latin squares in PLS(2, 3; n) by using permutations described by filled rows and intersections of filled rows and columns. We find that all partial latin squares in PLS(2, 3;n), where n is sufficiently large, can be completed if such a reduction can be completed. We also show that all partial latin squares in PLS(2, 3; n) where the intersection of filled rows and columns form a latin rectangle have completions for n ≥ 8.

The Internet of Things (IoT) is an important and expanding technology used for a large variety of applications to monitor and automate processes. The aim of this thesis is to present a way to find and assign locally unique IDs to access points (APs) in enormous wireless IoT systems where mobile tags are traversing the network and communicating with multiple APs simultaneously. This is done in order to improve the robustness of the system and increase the battery time of the tags. The resulting algorithm is based on transforming the problem into a graph coloring problem and solving it using approximate methods. Two metaheuristics: Simulated annealing and tabu search were implemented and compared for this purpose. Both of these showed similar results and neither was clearly superior to the other. Furthermore, the presented algorithm can also exclude nodes from the coloring based on the results in order to ensure a proper solution that also satisfies a robustness criterion. A metric was also created in order for a user to intuitively evaluate the quality of a given solution. The algorithm was tested and evaluated on a system of 222 APs for which it produced good results.