This thesis centers around a generalization of the classical discrete Fourier transform. We first present a general diagrammatic approach to the construction of efficient algorithms for computing the Fourier transform of a function on a finite...
In the past decade, the use of ordinal patterns in the analysis of time series and dynamical systems has become an important tool. Ordinal patterns (otherwise known as a permutation patterns) are found in time series by taking n data points at...
In Chapter 2 we look at the distribution of permutation statistics in the context of pattern-avoiding permutations. The first part of this chapter deals with a recursively defined bijection of Robertson [37] between 123- and 132-avoiding...
Partially ordered sets and permutations are combinatorial structures having vast applications in theoretical computer science. In this thesis, we study various computational and algorithmic problems related to these structures. The first chapter of...
We study the bijective combinatorics of reduced words. These are fundamental objects in the study of Coxeter groups. We restrict our focus to reduced words of permutations and signed permutations. Our results can all be situated within the context...
In this thesis, we characterize and enumerate the permutations which are realized by the orbits of signed shifts, a family of discrete dynamical systems on words. The permutations, which are called patterns of the signed shifts, are given by the...
In the Firefighter Problem, a fire starts at a vertex of a graph, and in discrete time units, it spreads from burned vertices to their neighbors, unless they are protected by one of the f firefighters that are deployed every turn. Once burned or...
We start by introducing avoidance coupling of Markov chains, with an overview of existing results. We then introduce and motivate a new notion, uniform coupling. We show that the only Markovian avoidance coupling on a cycle is of this type, and...
Polynomials. Finite fields (Algebra). Algebraic functions. Number theory.
The ring of univariate polynomials over a finite field shares many foundational arithmetic properties with the ring of rational integers. This similarity makes it possible for many problems in elementary number theory to be translated 'through the...
We examine variations of cops and robbers games on graphs. Our goals are to introduce some randomness into their study, and to estimate (expected) capture time. We show that a cop chasing a random walker can capture him in expected time n + o(n)....