Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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 …

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 …