Discrete Mathematics and Combinatorics Commons^™

On The Number Of Ways To Express A Set As A Union Of Individually Interesting Sets, Alison Watson

Master's Theses

In a dataset that contains what ought rightly to be several distinct datasets placed in juxtaposition with each other, grouping datapoints based on observed similarities can be done in many ways. Topological Data Analysis (TDA) is a field of math that seeks to impose geometric structure onto datasets, thereby translating problems in statistics to problems in geometry or topology. A common truism in this field is “Data has shape and shape has meaning.” In this thesis, we use combinatorial and categorical arguments to demonstrate some shortcomings of a TDA approach on a class of inverse problems inspired by marine wildlife …

From Total Domination To Graph Coloring, Sawyer Isaac Osborn

Dissertations

A question involving a chess piece called a prince on the 8×8 chessboard leads to a concept in graph theory involving total domination. We say a vertex u in a graph G totally dominates a vertex v if u is adjacent to v. A subset S of the vertex set of a graph G is a total dominating set for G if every vertex in G is totally dominated by at least one vertex of S. If S is a total dominating set of G, then σ_S(v) denotes the number of …

Equitable Decompositions: A Gateway To Spectral Theory Through Graph Automorphisms, Daniel Ford

Master's Theses

Graphs with symmetry appear throughout mathematics and its applications, from the structure of molecules and network design to combinatorial game theory. A central question in spectral graph theory is how to compute or characterise the eigenvalues of the matrices associated with such graphs. Classical decomposition methods, such as diagonalisation or Jordan normal form, accomplish this but only once some spectral information is already known. A different approach, introduced by Barrett et al. (2015), uses the automorphisms of a graph to block-diagonalise its adjacency matrix without any prior spectral information. Because one of the resulting summands is always the quotient matrix …

Comparing The Sensitivity And Degree Of Boolean Functions Via The Hypercube, Anne-Caroline Rupp

University Honors Theses

This thesis studies three complexity measures of total Boolean functions f:{0,1}ⁿ → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal.

The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry …

Quiver Of Affine Monoid Of A Vector Space Over Finite Field, James Junie Chen Cleary

Dissertations, Theses, and Capstone Projects

In this paper, we study the quiver of the complex monoid algebra CAFF(n, q). There are n + 1 maximal subgroups of AFF(n, q), each isomorphic to AGL(k, q) for some 0 ≤ k ≤ n. Every irreducible representation of CAFF(n, q) arises from a character of CAGL(k, q) for a suitable k. Thus, we study two different approaches to classifying the characters of CAGL(k, q). Next, we compute the full quiver Q(CAFF(n, q)). Finally, we show that this quiver is a disjoint union of straight-line paths and that its basic algebra has radical square zero. Hence, it has finite …

Relation Subspaces In Vertex Operator Algebras: Residue Generators For O_N^\Circ(V) And Intersections With (L(−1) +L(0))V, Junghyun Kim

Undergraduate Research Journal

We study the relation subspace 𝑂◦𝑛 (𝑉) that appears in the definition o f the level-𝑛 Zhu algebra 𝐴𝑛 (𝑉) = 𝑉/𝑂𝑛 (𝑉), where 𝑂𝑛 (𝑉) = 𝑂𝐿 (𝑉) + 𝑂◦𝑛 (𝑉) and 𝑂𝐿 (𝑉) =(𝐿(−1) + 𝐿(0))𝑉. Using residue calculus, we introduce operators 𝑅𝑛,𝑘 that encode the circle products 𝑢◦𝑛 𝑣 and prove explicit change-of-generators formulas between the standard generators (𝑢−𝑚1)◦𝑛 𝑣 and the residue generators 𝑢 𝑅𝑛,0𝑣, together with a binomial inversion. These identities provide a practical framework for computing 𝑂◦𝑛 (𝑉), especially in strongly generated VOAs. As progress toward understanding the overlap 𝑂◦𝑛 (𝑉) ∩ 𝑂𝐿 (𝑉), …

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 …

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 …

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 …

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 …

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.