The main topic of this thesis is combinatorics on words. The field of combinatorics on words dates back at least to the beginning of the 20th century when Axel Thue constructed an infinite squarefree sequence over a ternary alphabet. From this celebrated result also emerged the subfield of repetition in words which is the main focus of this thesis. One basic tool in the study of repetition in words is the iteration of morphisms. In Chapter 1, we introduce this tool among other basic notions. In Chapter 2, we see applications of iterated morphisms in several examples. The second half of the chapter contains a survey of results concerning Dejean's conjecture. In Chapter 3, we generalize Dejean's conjecture to circular factors. We see several applications of iterated morphism in this chapter. We continue our study of repetition in words in Chapter 4, where we study the length of the shortest repetition-free word in regular languages. Finally, in Chapter 5, we conclude by presenting a number of open problems.

In this dissertation, we examine the nature of embeddings with regard to both combinatorial and geometric configurations. A combinatorial [r,k]-configuration is a collection of abstract points and sets (referred to as blocks) such that each point is a member of r blocks, each block is of size k, and these objects satisfy a linearity criterion: no two blocks intersect in more than one point. A geometric configuration requires that the points and blocks be realized as points and lines within the Euclidean plane. We provide improvements on the current bounds for the asymptotic existence of both combinatorial and geometric configurations. In addition, we examine the largely new problem of embedding configurations within larger configurations possessing regularity properties. Additionally, previously undiscovered geometric [r,k]-configurations are found as near-coverings of combinatorial configurations. / Graduate

Side channel attacks, where an attacker learns some physical information about the state of a device, are one of the ways in which cryptographic schemes are broken in practice. "Provably secure" schemes are subject to these attacks since the traditional models of security do not account for them. The theoretical community has recently proposed leakage resilient cryptography in an effort to account for side channel attacks in the security model. This thesis provides an in-depth look into what security guarantees public key leakage resilient schemes provide in practice.

Immanants are a generalization of the well-studied determinant and permanent. Although the combinatorial interpretations for the determinant and permanent have been studied in excess, there remain few combinatorial interpretations for the immanant. The main objective of this thesis is to consider the immanant, and its possible combinatorial interpretations, in terms of recursive structures on the character. This thesis presents a comprehensive view of previous interpretations of immanants. Furthermore, it discusses algebraic techniques that may be used to investigate further into the combinatorial aspects of the immanant. We consider the Temperley-Lieb algebra and the class of immanants over the elements of this algebra. Combinatorial tools including the Temperley-Lieb algebra and Kauffman diagrams will be used in a number of interpretations. In particular, we extend some results for the permanent and determinant based on the $R$-weighted planar network construction, where $R$ is a convenient ring, by Clearman, Shelton, and Skandera. This thesis also presents some cases in which this construction cannot be extended. Finally, we present some extensions to combinatorial interpretations on certain classes of tableaux, as well as certain classes of matrices.

A new algorithm for the enumeration of derivative superstructures of a crystal is presented. The algorithm will help increase the efficiency of computational material design methods such as cluster expansion by increasing the size and diversity of the types of systems that can be modeled. Modeling potential alloys requires the exploration of all possible configurations of atoms. Additionally, modeling the thermal properties of materials requires knowledge of the possible ways of displacing the atoms. One solution to finding all symmetrically unique configurations and displacements is to generate the complete list of possible configurations and remove those that are symmetrically equivalent. This approach, however, suffers from the combinatoric explosion that happens when the supercell size is large, when there are more than two atom types, or when atomic displacements are included in the system. The combinatoric explosion is a problem because the large number of possible arrangements makes finding the relatively small number of unique arrangements for these systems impractical. The algorithm presented here is an extension of an existing algorithm [Hart & Forcade (2008a), Hart & Forcade (2009a), Hart et al. (2012a) Hart, Nelson, & Forcade] to include the extra configurational degree of freedom from the inclusion of displacement directions. The algorithm makes use of another recently developed algorithm for the Pólya [Pólya & Read (1987), Pólya (1937), Rosenbrock et al.(2015) Rosenbrock, Morgan, Hart, Curtarolo, & Forcade] counting theorem to inform the user of the total number of unique arrangements before performing the enumeration and to ensure that the list of unique arrangements will fit in system memory. The algorithm also uses group theory to eliminate large classes of arrangements rather than eliminating arrangements one by one. The three major topics of this paper will be presented in this order, first the Pólya algorithm, second the new algorithm for eliminating duplicate structures, and third the algorithms extension to include displacement directions. With these tools, it is possible to avoid the combinatoric explosion and enumerate previously inaccessible systems, including those that contain displaced atoms.

Nous déterminons dans cette thèse l'image des groupes de Artin associés à des groupes de Coxeter irréductibles dans leur algèbre de Iwahori-Hecke finie associée. Cela a été fait en type A dans des articles de Brunat, Marin et Magaard. Dans le cas générique, la clôture de l'image de Zariski a été déterminée dans tous les cas par Marin. L'approximation forte suggère que les résultats devraient être similaire dans le cas fini. Il est néanmoins impossible d'utiliser l'approximation forte sans utiliser de lourdes hypothèses et limiter l'étendue des résultats. Nous démontrons dans cette thèse que les résultats sont similaires mais que de nouveaux phénomènes interviennent de par la complexification des extensions de corps considérées. Les arguments principaux proviennent de la théorie des groupes finis. Nous utiliserons notamment un Théorème de Guralnick et Saxl qui utilise la classification des groupes finis simples pour les représentations de hautes dimensions. Ce théorème donne des conditions pour que des sous-groupes de groupes linéaires soient des groupes classiques dans une représentation naturelle. En petite dimension, nous utiliserons la classification des sous-groupes maximaux des groupes classiques de Bray, Holt et Roney-Dougal pour les cas les plus compliqués / In this doctoral thesis, we will determine the image of Artin groups associated to all finite irreducible Coxeter groups inside their associated finite Iwahori-Hecke algebra. This was done in type A in articles by Brunat, Marin and Magaard. The Zariski closure of the image was determined in the generic case by Marin. It is suggested by strong approximation that the results should be similar in the finite case. However, the conditions required to use are much too strong and would only provide a portion of the results. We show in this thesis that they are but that new phenomena arise from the different field factorizations. The techniques used in the finite case are very different from the ones in the generic case. The main arguments come from finite group theory. In high dimension, we will use a theorem by Guralnick-Saxl which uses the classification of finite simple groups to give a condition for subgroups of linear groups to be classical groups in a natural representation. In low dimension, we will mainly use the classification of maximal subgroups of classical groups obtained by Bray, Holt and Roney-Dougal for the complicated cases

No description available.

In recent years it has been shown that the folding pattern of an RNA molecule plays an important role in its function, likened to a lock and key system. γ-structures are a subset of RNA pseudoknot structures filtered by topological genus that lend themselves nicely to combinatorial analysis. Namely, the coefficients of their generating function can be approximated for large n. This paper is an investigation into the length-spectrum of the longest block in random γ-structures. We prove that the expected length of the longest block is on the order n - O(n^1/2). We further compare these results with a similar analysis of the length-spectrum of rainbows in RNA secondary structures, found in Li and Reidys (2018). It turns out that the expected length of the longest block for γ-structures is on the order the same as the expected length of rainbows in secondary structures. / Master of Science / Ribonucleic acid (RNA), similar in composition to well-known DNA, plays a myriad of roles within the cell. The major distinction between DNA and RNA is the nature of the nucleotide pairings. RNA is single stranded, to mean that its nucleotides are paired with one another (as opposed to a unique complementary strand). Consequently, RNA exhibits a knotted 3D structure. These diverse structures (folding patterns) have been shown to play important roles in RNA function, likened to a lock and key system. Given the cost of gathering data on folding patterns, little is known about exactly how structure and function are related. The work presented centers around building the mathematical framework of RNA structures in an effort to guide technology and further scientific discovery. We provide insight into the prevalence of certain important folding patterns.

This thesis is written as a single source introduction to Ramsey Theory for advanced undergraduates and graduate students. / Master of Science

In this dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we focus on some new automata that do not seem to have occurred much in the literature, that of solvability of mazes. For our model, a maze is a countable strongly connected digraph together with a proper colouring of its edges (without two edges leaving a vertex getting the same colour) and two special vertices: the origin and the destination. A pointer or robot starts in the origin of a maze and moves naturally between its vertices, according to a sequence of specific instructions from the set of all colours; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. We call such a finite or infinite sequence of instructions an algorithm. In particular, one of the most interesting and very natural sets of mazes occurs when our maze is the square lattice Z2 as a graph with some of its edges removed. Obviously, we need to require that the origin and the destination vertices are in the same connected component and it is very natural to take the four instructions to be the cardinal directions. In this set-up, we make progress towards a beautiful problem posed by Leader and Spink in 2011 which asks whether there is an algorithm which solves the set of all such mazes. Next, we address a problem regarding symmetric chain decompositions of posets. We ask if there exists a symmetric chain decomposition of a 2 × 2 × ... × 2 × n cuboid (k 2’s) such that no chain has a subchain of the form (a1,...,ak,0) ≺ ... ≺ (a1,...,ak,n−1)? We show this is true precisely when k≥5 and n≥3. Thisquestion arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this chapter unexpectedly resolves the most difficult case of previous work by Spink on almost orthogonal symmetric chain decompositions (2017) which makes progress on a conjecture of Shearer and Kleitman. Moreover, we generalize our methods to other finite graded posets. Finally, we address two different problems in extremal combinatorics related to mathematical physics. Firstly, we study metastable states in the Ising model. We propose a general model for 1-flip spin systems, and initiate the study of extremal properties of their stable states. By translating local stability conditions into Sperner- type conditions, we provide non-trivial upper bounds which are often tight for large classes of such systems. The last topic we consider is a deterministic bootstrap percolation type problem. More specifically, we prove several extremal results about fast 2-neighbour percolation on the two dimensional grid.