Combinatorial analysis

The goal of this dissertation is to estimate the precise asymptotics for the number of geometric equivalence classes of Morse functions on the 2-sphere. Our approach involves utilizing the Lagrange inversion formula, Cauchy’s coefficient formula, and the saddle point method for the asymptotic analysis of contour integrals to analyze the generating function derived by L. Nicolaescu, expressed as the inverse of an elliptic integral. We utilize complex analysis, nonlinear functional analysis in infinite sequence spaces, and interval arithmetic to write all the necessary MATLAB programs that validate our results. This work answers questions posed by Arnold and Nicolaescu, furthering our understanding of the topological properties of Morse functions on two-dimensional manifolds. It also demonstrates the effectiveness of a computer assisted approach for asymptotic analysis.

An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes.

As quantum computers continue to develop, they pose a threat to cryptography since many popular cryptosystems will be rendered vulnerable. This is because the security of most currently used asymmetric systems requires the computational hardness of the integer factorization problem, the discrete logarithm or the elliptic curve discrete logarithm problem. However, there are still some cryptosystems that resist quantum computing. We will look at code-based cryptography in general and the McEliece cryptosystem specifically. Our goal is to understand the structure behind the McEliece scheme, including the encryption and decryption processes, and what some advantages and disadvantages are that the system has to offer. In addition, using the results from Courtois, Finiasz, and Sendrier's paper in 2001, we will discuss a digital signature scheme based on the McEliece cryptosystem. We analyze one classical algebraic attack against the security analysis of the system based on the distinguishing problem whether the public key of the McEliece scheme is generated from a generating matrix of a binary Goppa code or a random binary matrix. The idea of the attack involves solving an algebraic system of equations and we examine the dimension of the solution space of the linearized system of equations. With the assistance from a paper in 2010 by Faugere, Gauthier-Umana, Otmani, Perret, Tillich, we will see the parameters needed for the intractability of the distinguishing problem.

A well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger, Mireille Bousquet-Mlou, Thomas Prellberg, Neal Madras, Gordon Slade, Agnes Dit- tel, E.J. Janse van Rensburg, Harry Kesten, Stuart G. Whittington, Lincoln Chayes, Iwan Jensen, Arthur T. Benjamin, and many others. More than three hundred papers and a few volumes of books were published in this area. A SAW is interesting for simulations because its properties cannot be calculated analytically. Calculating the number of self-avoiding walks is a common computational problem. A recently proposed model called prudent self-avoiding walks (PSAW) was first introduced to the mathematics community in an unpublished manuscript of Pra, who called them exterior walks. A prudent walk is a connected path on square lattice such that, at each step, the extension of that step along its current trajectory will never intersect any previously occupied vertex. A lattice path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. We will discuss some enumerative problems in self-avoiding walks, lattice paths and walks with several step vectors. Many open problems are posted.

Famous mathematician Paul Erdèos conjectured the existence of infinite sequences of symbols where no two adjacent subsequences are permutations of one another. It can easily be checked that no such sequence can be constructed using only three symbols, but as few as four symbols are sufficient. Here, we expand this concept to include sequences that may contain 'do not know'' characters, called holes. These holes make the undesired subsequences more common. We explore both finite and infinite sequences. For infinite sequences, we use iterating morphisms to construct the non-repetitive sequences with either a finite number of holes or infinitely many holes. We also discuss the problem of using the minimum number of different symbols.