Discrete Mathematics and Combinatorics Commons^™

Greedy Algorithms And Matroids, Kiri M. Strack

LSU Master's Theses

In a connected graph with weights on the edges, a minimum-weight spanning tree can be obtained by repeatedly choosing minimum-weight edges while avoiding choosing the edge set of any cycle. This algorithm is known as Kruskal’s Algorithm, although it was first introduced by Boruvka in 1926. Prim introduced an alternative algorithm in which, at each step, the chosen set of edges forms a connected graph. Both of these algorithms make locally optimal choices that eventually yield a global optimum. This thesis considers how these algorithms can be extended to matroids. In particular, it is shown that matroids are exactly the …

Largest 2-Regular Subgraphs In Complete S-Partite Graphs, Yiyang Jiang

McKelvey School of Engineering Graduate Student Theses & Dissertations

In this thesis, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in studying largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. …

Numerical And Harmonic Analysis Of Simplex Number Parity, Hunter Dm Hannula

All NMU Master's Theses

The primary object of this thesis is the study of periodicity in the parity of simplex numbers by number-theoretic and harmonic methods. The regular d-simplex numbers are introduced geometrically, arithmetically, and combinatorially. We demonstrate that all sequences indexing even d-simplex numbers are defined by finitely many congruences in a single modulus, and are thus quasiperiodic. We therefore show that these "even index-sequences" are  particular elements in an affine space of functions, providing a natural decomposition result. We then introduce the discrete Fourier transform to construct the periodic parts of each index sequence, enabling the development of explicit forms for the …

A New Approach To Generate Combinatorial Patterns In Logical Analysis Of Data And Its Application To Predict College Retention, Salihah Ahmed E. Jaafari

Theses and Dissertations

Student retention and degree completion remain central challenges for higher-education institutions, with significant implications for student success, institutional effectiveness, and public accountability. While advances in predictive analytics have enabled earlier identification of students at risk of withdrawal, many commonly used machine learning approaches suffer from limited interpretability, constraining their practical usefulness for advising, intervention, and policy decision making. This dissertation addresses the problem of predicting student persistence by developing and evaluating optimization based, interpretable classification models within the Logical Analysis of Data (LAD) framework. Building on existing LAD formulations, this research introduces two novel pattern generation models, the Best Term …

Sumset Lower Bounds In Abelian Groups, Van T. Huynh

Honors Theses

This thesis investigates sumset lower bounds across discrete and continuous settings. We begin with general inequalities in torsion-free abelian groups and then specialize to the integers modulo prime p, where we present the Cauchy–Davenport Theorem, which establishes the bound ∣A+B∣≥min(p,∣A∣+∣B∣−1). The equality case is further examined via Vosper's Theorem, which characterizes subsets attaining this bound as arithmetic progressions under suitable conditions. The continuous analogue in Euclidean spaces is then considered, where cardinality is replaced by Lebesgue measure. In this setting, the Brunn–Minkowski Inequality provides a sharp lower bound for the Lebesgue measure of A+B and serves as a geometric counterpart …

On The Algebraicity Of The Tic-Tac-Toe Matroid And Homogeneous Mixed Bowtie Systems, Benjamin R. Allen

Electronic Theses and Dissertations

This thesis is presented in two parts. First, we explore whether the class of algebraic matroids is closed under duality, a decades-old open question. We consider the Tic-Tac-Toe matroid as a potential candidate to answer the open question. The Tic-Tac-Toe matroid is known to satisfy many of the necessary conditions for a matroid to be algebraic and has a non-algebraic dual.  Second, we focus on decompositions of the complete mixed graph into mixed bowties. A complete mixed graph has between every pair of vertices an undirected edge and antiparallel arcs. A mixed bowtie is a graph consisting of two 3-cycles …

Counting Hamiltonian Cycles In Quartic Circulant Graphs, Allison Hilliard

Seaver College Research And Scholarly Achievement Symposium

We consider the problem of counting Hamiltonian cycles in circulant graphs $C^K_n$ where $n$ is the number of vertices and $K$ is a set containing elements that correspond to the allowed edges in the circulant graphs. After sorting the cycles by a topological invariant called the winding number, we use a modified transfer matrix method to convert local data into global structures. The result is a generating function that counts the number of Hamiltonian cycles in a circulant graph with $n$ vertices. The results for $K=\{1,2\}$ and $K=\{1,3\}$ have been found by previous authors. We focus on the case where …

Irreversible K-Threshold Dynamics On Corona And Base-B Corona Product Graphs, Eric J. Moon, Soumya Bhoumik, Paul Flesher

SACAD: Scholarly Activities

This poster studies the irreversible k-threshold process on corona-type graph products, where a vertex becomes colored once at least k of its neighbors are colored and then remains colored permanently. We focus on corona, double corona, and base-b corona product graphs built from cycles and complete graphs, with particular attention to how graph structure affects complete activation from a minimum seed set.

A generalized reduction lemma is used to relate threshold dynamics on layered corona graphs to smaller residual graphs, yielding explicit formulas for the irreversible k-threshold conversion number on both corona and double corona families. The …

Extremal Connectivity In Graphs And Matroids, Yiwei Ge

LSU Doctoral Dissertations

Connectivity is a central theme in both graph theory and matroid theory. This dissertation investigates extremal connectivity in graphs and matroids, with emphasis on unavoidable structures and minimal connectivity phenomena.

Chapter 2 introduces cycle-contraction minors of graphs and investigates their structural properties. We establish a connection between cc-minors and induced subgraphs via graph duality. The main result gives an unavoidable-families characterization for cc-minors of sufficiently large loopless $2$-connected graphs.

Chapter 3 studies super-minimally $3$-connected graphs, namely $3$-connected graphs that have no proper $3$-connected subgraphs. We establish extremal bounds on structural parameters of these graphs, including the minimum number of degree-$3$ …

A 4-Dimensional Rubik’S Cube You Can Hold: How It’S Possible And The Math Behind It, Eric J. Moon

SACAD: Scholarly Activities

This poster examines the physical 2x2x2x2, a hand-held realization of a 4-dimensional Rubik’s Cube invented by Melinda Green. Unlike most higher-dimensional twisty puzzles, which exist only as software simulations, this puzzle provides a physical model for exploring 4-dimensional rotation, symmetry, and solving methods. The poster introduces the structure of the puzzle, its canonical move system, and several algebraic ideas that help explain how scrambling and solving work.

From a mathematical perspective, the puzzle can be studied using group actions, commutators, conjugation, and combinatorial counting. In particular, the number of reachable states depends on corner permutations, corner orientations, parity restrictions, twist …

Circuits And Enumeration Problems For Matroids, Christine H. Cho

LSU Doctoral Dissertations

This dissertation is a collection of work concerning the structure and enumeration of circuits and other distinguished sets in a matroid. The Tutte polynomial, recognized as the universal deletion-contraction invariant in matroid and graph theory, is a natural starting point when considering enumeration problems for matroids. The main result in Chapter 2 generalizes a theorem of Dean Lucas concerning the Tutte polynomial and its behavior under rank-preserving weak maps. This generalization provides an avenue for comparing the numbers of circuits, bases, rank-k flats, and hyperplanes of a matroid containing an element given two distinct, yet related, elements.

Chapter 3 addresses …

Algorithm Performance In The Search For Hamiltonian Cycles, Chance Davis

Honors Theses

The Hamiltonian cycle problem is ubiquitous in both computer science and graph theory: Given a connected graph, a solution would either confirm the existence of a cycle which visits each vertex only once or its nonexistence. The importance of this problem, as well as its difficulty, is described in the Clay Mathematics Institute’s Millenium Prize Problems and Karp’s 21 NP-complete problems. Despite its “hardness,” solutions to the Hamiltonian cycle problem are desired in logistics, electronic circuit design, and network routing, among other fields. In this work, we benchmark a promising exhaustive enumeration algorithm on various graphs, including ones derived from …

On The Extreme Complexity Of Certain Nearly Regular Graphs, Gregory P. Constantine, Gregory C. Magda

Theory & Applications of Graphs

The complexity of a graph is the number of its labeled spanning trees. It is demonstrated that the seven known triangle-free strongly regular graphs are graphs of maximal complexity among all graphs of the same order and degree; their complements are shown to be of minimal complexity. A generalization to nearly regular graphs with two distinct eigenvalues of the Laplacian is presented. Conjectures and applications of these results to biological problems on neuronal activity are described.

Cycle-Based Characterizations Of The Cycle Completable Graphs, Terry A. Mckee

Theory & Applications of Graphs

Cycle completable graphs were originally defined to answer matrix completion problems and have since received diverse graph-theoretic descriptions, in spite of not directly mentioning cycles. This paper characterizes such graphs by their chordless cycles never having ``bridges'' (as defined in H.-J. Voss's 1991 monograph {\em Cycles and Bridges in Graphs\/}) that have more than two vertices of attachment in the cycle. This approach is then related to the well-studied, yet seemingly quite distinct, classes of chordal graphs and series-parallel graphs. This is done by allowing chords to be ``bridges'' that have exactly two vertices of attachment.

Forbidden Induced Restrictions And Unavoidable Minors In Matroids, Matthew P. Mizell

LSU Doctoral Dissertations

Targets are matroids that arise from a nested sequence of flats in a projective geometry. This class of matroids was introduced by Nelson and Nomoto, who found the forbidden induced restrictions for binary targets. In this dissertation, their result is generalized to targets arising from projective geometries over $GF(q)$. In addition, targets arising from nested sequences of affine flats are introduced and the forbidden induced restrictions for these affine targets are determined.

In 1963, Halin and Jung proved that every simple graph with minimum degree at least four has $K_5$ or $K_{2,2,2}$ as a minor. Mills and Turner proved an …

(Si16-07) Computing The Kirchhoff Index And The Wiener Index Of Spiro Para Hexagonal Cylinder Chain, Md Selim Reja, Sk. Md. Abu Nayeem

Applications and Applied Mathematics: An International Journal (AAM)

In graph theory, the Kirchhoff index serves as a metric to evaluate the complexity of a graph. It is determined by adding up the resistance distances between every pair of vertices in the graph. In a network created from the given graph by substituting each edge by a unit resistor, the resistance distance between a pair of specified vertices is equivalent to the electrical resistance between them in the constructed network. Basically, it measures the convenience with which data or flow can move between various locations in a network that the graph represents. In terms of graph matrices, the Kirchhoff …

Demystifying Hardware Formal Verification For Undergraduate Education: A Risc-V Processor Case Study With Coursework Implementation, Riley A. Peters

Master's Theses

Hardware verification engineers apply formal methods to prove that a digital device always behaves according to its specification. This differs from traditional functional verification, in which engineers establish correctness by repeatedly sending test inputs to the device and comparing the outputs against a reference model. With the growing complexity of integrated circuits, the demand for digital verification engineers with formal methods experience has continued to increase. However, California Polytechnic State University: San Luis Obispo's current curriculum lacks dedicated material to prepare students for these roles.

This thesis seeks to address the lack of formal methods material through two efforts. First, …

Gliders On The Sca Model, Alexa Renner

Mathematical Sciences Technical Reports (MSTR)

The Stranded Cellular Automata (SCA) model consists of a grid of cells which can each contain between zero and two strands apiece and two turning rules that control when strands turn and when they cross. While patterns on this model have been studied previously, such research has not needed an algebraic description of the model. We provide a formal algebraic definition of patterns on the model, define gliders on the model in a way which is semi-compatible with definitions of gliders in other cellular automata models, and classify all 1- and 2-stranded gliders on this model. In addition, we prove …

An Introduction To Modern Conversations On Knot Invariants, Stella Shah

Scripps Senior Theses

Knot Theory is a vast and diverse subfield of modern mathematics involving the classification and abstraction of knots and links. In this thesis, we wish to provide the necessary background for and an explanation of two papers in different subfields of knot theory, The Forbidden Quiver of a Link, and Biquandle Fares and Link Invariants.

In Chapter I, we begin with an introduction to knot theory and knot invariants. We continue to present the example of Fox Colorings, and conclude the chapter with an example of the Fox Coloring Number Invariant.

In Chapter II, we explore the derivation and utilization …

Balanced Multi-Party Tournament Designs, Parsa Nematollahe

Honors College Theses

This paper introduces Multi-Party Tournament (MPT) designs that generalize established combinatorial structures, including Whist, Pitch, and Generalized Whist tournament designs. This work will formally define MPTs, establish the fundamental properties of resolvability, fullness, and balance, and formulate a mathematical and algorithmic foundation for multi-party tournament scheduling. The primary contributions of this research are the presentation of necessary and sufficient existence conditions for MPTs across various properties and parameters, the identification of connections between MPTs and other fields of mathematics such as combinatorial design theory, graph theory, and probability theory, and the investigation of MPT construction algorithms, including tree-search, finite-field constructions, …