Digital Commons Network^™

The Earth Mover's Distance Through The Lens Of Algebraic Combinatorics, William Quentin Erickson

Theses and Dissertations

The earth mover's distance (EMD) is a metric for comparing two histograms, with burgeoning applications in image retrieval, computer vision, optimal transport, physics, cosmology, political science, epidemiology, and many other fields. In this thesis, however, we approach the EMD from three distinct viewpoints in algebraic combinatorics. First, by regarding the EMD as the symmetric difference of two Young diagrams, we use combinatorial arguments to answer statistical questions about histogram pairs. Second, we adopt as a natural model for the EMD a certain infinite-dimensional module, known as the first Wallach representation of the Lie algebra su(p,q), which arises in the Howe …

Extensions And Bijections Of Skew-Shaped Tableaux And Factorizations Of Singer Cycles, Ga Yee Park

Doctoral Dissertations

This dissertation is in the field of Algebraic and Enumerative Combinatorics. In the first part of the thesis, we study the generalization of Naruse hook-length formula to mobile posets. Families of posets like Young diagrams of straight shapes and d-complete posets have hook-length product formulas to count linear extensions, whereas families like Young diagrams of skew shapes have determinant or positive sum formulas like the Naruse hook-length formula (NHLF). In 2020, Garver et. al. gave determinant formulas to count linear extensions of a family of posets called mobile posets that refine d-complete posets and border strip skew shapes. We give …

Minimal Inscribed Polyforms, Jack Hanke

Honors Scholar Theses

A polyomino of size n is constructed by joining n unit squares together by their edge to form a shape in the plane. This thesis will first examine the formal definition of a polyomino and the common equivalence classes polyominos are enumerated under. We then turn to polyomino families, and provide exact enumeration results for certain families, including the minimal inscribed polyominos. Next we will generalize polyominos to polyforms, and provide novel formulae for polyform analogues of minimal inscribed polyominos. Finally, we discuss some further questions concerning minimal inscribed polyforms.

Characterizations Of Certain Classes Of Graphs And Matroids, Jagdeep Singh

LSU Doctoral Dissertations

``If a theorem about graphs can be expressed in terms of edges and cycles only, it probably exemplifies a more general theorem about matroids." Most of my work draws inspiration from this assertion, made by Tutte in 1979.

In 2004, Ehrenfeucht, Harju and Rozenberg proved that all graphs can be constructed from complete graphs via a sequence of the operations of complementation, switching edges and non-edges at a vertex, and local complementation. In Chapter 2, we consider the binary matroid analogue of each of these graph operations. We prove that the analogue of the result of Ehrenfeucht et. al. does …

Finding Optimal Cayley Map Embeddings Using Genetic Algorithms, Jacob Buckelew

Honors Program Theses

Genetic algorithms are a commonly used metaheuristic search method aimed at solving complex optimization problems in a variety of fields. These types of algorithms lend themselves to problems that can incorporate stochastic elements, which allows for a wider search across a search space. However, the nature of the genetic algorithm can often cause challenges regarding time-consumption. Although the genetic algorithm may be widely applicable to various domains, it is not guaranteed that the algorithm will outperform other traditional search methods in solving problems specific to particular domains. In this paper, we test the feasibility of genetic algorithms in solving a …

Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler

Graduate Student Theses, Dissertations, & Professional Papers

In this study we present a novel algorithm, LASSO, for solving the unbounded and bounded subset sum problem. The LASSO algorithm was designed to solve the unbounded SSP quickly and to return all subsets summing to a target sum. As speed was the highest priority, we benchmarked the run time performance of LASSO against implementations of some common approaches to the bounded SSP, as well as the only comparable implementation for solving the unbounded SSP that we could find. In solving the bounded SSP, our algorithm had a significantly faster run time than the competing algorithms when the target sum …

Multicolor Ramsey And List Ramsey Numbers For Double Stars, Jake Ruotolo

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For a graph H, the k-color Ramsey number r(H; k) of H is the smallest integer n such that every k-edge-coloring of K_n contains a monochromatic copy of H. Despite active research for decades, very little is known about Ramsey numbers of graphs. This is especially true for r(H; k) when k is at least 3, also known as the multicolor Ramsey number of …