In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when a given tournament can be considered a 2-majority tournament. In this thesis, we prove, among other things, that the presence of an upset path in a tournament allows us to conclude the tournament is realizable as a 2-majority tournament.

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.

This paper will discuss the analogues between Leibniz's Harmonic Triangle and Pascal's Arithmetic Triangle by utilizing mathematical proving techniques like partial sums, committees, telescoping, mathematical induction and applying George Polya's perspective. The topics presented in this paper will show that Pascal's triangle and Leibniz's triangle both have hockey stick type patterns, patterns of sums within shapes, and have the natural numbers, triangular numbers, tetrahedral numbers, and pentatope numbers hidden within. In addition, this paper will show how Pascal's Arithmetic Triangle can be used to construct Leibniz's Harmonic Triangle and show how both triangles relate to combinatorics and arithmetic through the coefficients of the binomial expansion. Furthermore, combinatorics plays an increasingly important role in mathematics, starting when students enter high school and continuing on into their college years. Students become familiar with the traditional arguments based on classical arithmetic and algebra, however, methods of combinatorics can vary greatly. In combinatorics, perhaps the most important concept revolves around the coefficients of the binomial expansion, studying and proving their properties, and conveying a greater insight into mathematics.

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.

Let d > 0 be a fixed integer and let A ⊆ ℝd be a collection of n ≥ d + 2 points which we lift into ℝd+1. Further let k be an integer satisfying 0 ≤ k ≤ n-(d+2) and assign to each k-subset of the points of A a (regular) triangulation obtained by deleting the specified k-subset and projecting down the lower hull of the convex hull of the resulting lifting. Next, for each triangulation we form the characteristic vector defined by Gelfand, Kapranov, and Zelevinsky by assigning to each vertex the sum of the volumes of all adjacent simplices. We then form a vector for the lifting, which we call the k-compound GKZ-vector, by summing all the characteristic vectors. Lastly, we construct a polytope Σk(A) ⊆ ℝ|A| by taking the convex hull of all obtainable k-compound GKZ-vectors by various liftings of A, and note that $\Sigma_0(\A)$ is the well-studied secondary polytope corresponding to A. We will see that by varying k, we obtain a family of polytopes with interesting properties relating to Minkowski sums, Gale transforms, and Lawrence constructions, with the member of the family with maximal k corresponding to a zonotope studied by Billera, Fillamen, and Sturmfels. We will also discuss the case k = d = 1, in which we can provide a combinatorial description of the vertices allowing us to better understand the graph of the polytope and to obtain formulas for the numbers of vertices and edges present.

Consider a probability distribution on the permutations of n elements. If the probability of each permutation is proportional to θK, where K is the number of cycles in the permutation, then we say that the distribution generates a θ-biased random permutation. A random permutation is a special θ-biased random permutation with θ = 1. The mth moment of the rth longest cycle of a random permutation is Θ(nm), regardless of r and θ. The joint moments are derived, and it is shown that the longest cycles of a permutation can either be positively or negatively correlated, depending on θ. The mth moments of the rth shortest cycle of a random permutation is Θ(nm−θ/(ln n)r−1) when θ < m, Θ((ln n)r) when θ = m, and Θ(1) when θ > m. The exponent of cycle lengths at the 100qth percentile goes to q with zero variance. The exponent of the expected cycle lengths at the 100qth percentile is at least q due to the Jensen’s inequality, and the exact value is derived.

A permutation array, represented by PA(n, d), is a subset of Sn such that any two distinct elements have a distance of at least d where d is the number of differing positions. We analyze the upper and lower bounds of permutation codes with distance equal to 4. An optimization problem on Young diagrams is used to improve the upper bound for almost all n while the lower bound is improved for small values of n by means of recursive construction methods.

A permutation array, represented by PA(n, d), is a subset of Sn such that any two distinct elements have a distance of at least d where d is the number of differing positions. We analyze the upper and lower bounds of permutation codes with distance equal to 4. An optimization problem on Young diagrams is used to improve the upper bound for almost all n while the lower bound is improved for small values of n by means of recursive construction methods.

A permutation array, represented by PA(n, d), is a subset of Sn such that any two distinct elements have a distance of at least d where d is the number of differing positions. We analyze the upper and lower bounds of permutation codes with distance equal to 4. An optimization problem on Young diagrams is used to improve the upper bound for almost all n while the lower bound is improved for small values of n by means of recursive construction methods.

The main purpose of this thesis to examine the controllability and observability of the linear discrete fractional systems. First we introduce the problem and continue with the review of some basic definitions and concepts of fractional calculus which are widely used to develop the theory of this subject. In Chapter 3, we give the unique solution of the fractional difference equation involving the Riemann-Liouville operator of real order between zero and one. Additionally we study the sequential fractional difference equations and describe the way to obtain the state-space repre- sentation of the sequential fractional difference equations. In Chapter 4, we study the controllability and observability of time-invariant linear nabla fractional systems.We investigate the time-variant case in Chapter 5 and we define the state transition matrix in fractional calculus. In the last chapter, the results are summarized and directions for future work are stated.