Discrete Mathematics and Combinatorics Commons^™

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, …

Enumerating Matrices Of A Given Order Over Finite Fields, Thor Richard Gabrielsen

Honors Theses

This thesis derives a generating function that describes the matrices of a given multiplicative order over finite fields of a given order assuming that the order of a field is not a divisor of the desired order of the matrix. This is done by using the power series known as the cycle index derived from the rational canonical form. This index can be factored, and using the fact that the minimal polynomial divides some polynomial of the form x^k − 1 we can show that the minimal polynomial is squarefree. This sufficiently restricts the form of the rational canonical form …

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, …

Extensions Between Modules Defined By Lattice Paths In The Preprojective Algebra, Chloe Napier

Theses and Dissertations--Mathematics

In 2001, Fomin and Zelevinsky introduced cluster algebras which appear as coordinate rings of many varieties. We study cluster algebras coming from Richardson varieties. Leclerc gives a cluster structure on Richardson varieties using the representation theory of preprojective algebras. While this construction is very algebraic, we take a more combinatorial approach. The main goal is to find a combinatorial description for when certain cluster variables are compatible, or equivalently when modules defined by lattice paths in the preprojective algebra have trivial extensions. We extend the known results from Geiss, Leclerc, and Schröer that answer this question in the case of …

Combinatorial Models For Nonnegativity In Flag Varieties, Williem L. Rizer

Theses and Dissertations--Mathematics

The nonnegative Grassmannian admits a widely studied cell decomposition due to Alexander Postnikov, whose cells are indexed by positroids and modeled by several equivalent combinatorial objects. Subsequent work by authors including Lauren Williams, Suho Oh, and Carolina Benedetti has further developed the combinatorics and geometry of these structures. In this dissertation, we extend some of Postnikov’s combinatorial framework to the nonnegative flag variety. While cell decompositions in this setting were previously obtained, notably in work of Konstanze Rietsch, our focus is on providing new combinatorial models that make this structure more explicit and computationally tractable. We introduce flag positroid pipe …

Catalan And Hyper-Catalan Numbers: Combinatorial Applications To Polynomial Equations, Leilani Natale

Williams Honors College, Honors Research Projects

In this paper, we study Catalan numbers and their generalization, hyper-Catalan numbers, and explore how these sequences arise naturally in the context of solving polynomial equations using infinite power series. We begin by introducing the Catalan numbers through their combinatorial interpretation as triangulations of convex polygons. Using this geometric definition, we derive a relation whose recursive structure leads to a quadratic functional equation. Interpreting this relation as a formal power series equation allows us to express solutions to quadratic equations as infinite power series whose coefficients are given by the Catalan numbers. This framework is then extended by allowing polygon …

Small Antiperfect Steiner Triple Systems, Justin Z. Schroeder, Joshua Ganschow

Research & Publications

The cycle structure of Steiner triple systems (STS) has been well studied with regard to uniform STS and cycle switching. Of particular interest among uniform STS are perfect STS, in which every cycle graph consists of a single cycle. In this paper, we initiate the study of antiperfect STS, in which every cycle graph consists of a union of at least two cycles. We prove that an antiperfect STS(n) exists for all admissible n ≥ 15 and provide a complete listing of all antiperfect STS(n) for n ≤ 19 and all antiperfect STS(21) with a non-trivial automorphism. Furthermore, it is …

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 …

Dominating Hadwiger's Conjecture For 2k2-Free Graphs, Thomas Tibbetts

Honors Undergraduate Theses

A dominating K_t minor in a graph �� is a sequence (��₁,…,��_t) of pairwise disjoint non-empty connected subgraphs of ��, such that for 1≤��< ��≤��, every vertex in ��_j has a neighbor in ��_i. Replacing “every vertex in ��_j” by “some vertex in ��_j” retrieves the standard definition of a ��_t minor. The strengthened notion was introduced by Illingworth and Wood in 2024, who asked whether every graph with chromatic number �� contains a dominating ��_t minor. This is a substantial strengthening of the celebrated Hadwiger’s Conjecture, which asserts that every …

A New Parsimony-Based Method For Reconstructing Sequences Of Developmental Events And Estimating Rates Of Intraspecific Variation, With Applications To Trilobites, Alexander Benjamin Bradley

Graduate Theses, Dissertations, and Problem Reports (ETD)

Ontogenetic Sequence Analysis (OSA) is a method for reconstructing multiple sequences of abrupt phenotypic transformations (developmental events) for sampled populations of any kind of organism. It makes use of cladistic parsimony software to produce a network, or graph, whose vertices represent unique phenotypes at different stages of maturity (“semaphoronts”) and whose edges describe the developmental events occurring between semaphoronts. It is a powerful tool for constraining the range of developmental variation possible for a given species and generating sample statistics capable of identifying both the most common and the outlier ontogenetic sequences. However, OSA has seen little use since its …

Symmetry In Latin Hypercubes, Levi Neiburger

Theses and Dissertations

Let [n] = {1, ..., n}. A hypercube H of order n and dimension d is a d-dimensional array whose nᵈ cells are indexed by [n]ᵈ. A hyperplane in H is obtained by fixing one coordinate, while allowing the remaining d–1 coordinates to vary. We wish to color each cell of H from a palette of n^d-1 colors such that each hyperplane is polychromatic.

Our main result is the following. Let n be sufficiently large. There exists a symmetric coloring of the d-dimensional hypercubes of order n whose all hyperplanes are polychromatic if and only if: …

Exploring The Metric Dimension Of The Graph Representing A Four-Ring Polycyclic Aromatic Hydrocarbon: Interstellar 1-Cyanopyrene, Andrei Matthew V. Robino, Sebastian Alex C. Traviña, Karl Benedict P. Narag, Mark Anthony B. Casao, Helix Raven C. Llanes, Azriel C. Alejo, Jonel C. Celamor

Sinaya: A Philippine Journal for Senior High School Teachers and Students

A graph's metric dimension is a parameter that denotes the minimum possible number of vertices in a subset that gives each vertex in the graph a unique representation. Despite extensive research on the metric dimension of polycyclic aromatic hydrocarbons (PAHs), there is currently no focused analysis on the metric basis and metric dimension of 1-cyanopyrene. In chemistry, graphs can be used to depict molecular structures. In this study, graph theory, specifically the concept of metric dimensions, is applied to the molecular structure of 1-cyanopyrene, which was detected in space for the first time in 2024. 1-cyanopyrene is a molecule made …

A Comprehensive Study Of Clique Graphs And Clique Regular Graphs, Connor Phillips

Senior Honors Projects, 2020-current

If Γ is a graph for which every edge is in exactly one clique of order ω, then one can form a new graph with vertex set equal to these cliques.  This is a generalization of the line graph of Γ.  We discover many general results and classifications related to these clique graphs that will be useful to researchers studying graphs with this property. In particular, we find bounds on the spectrum of Γ (with exact results when Γ is k-regular) and some complete classifications when Γ is strongly regular. We apply our results to derive novel information about the …

A Leslie System For A Demographic Simulation: From An Actuarial Point Of View, David Kings

Electronic Theses and Dissertations

This thesis develops a discrete stochastic linear systems interpretation of age–stage demographic evolution grounded in Leslie operators and realized in a discrete-event simulation implemented with salabim. The central claim is that one annual cycle of the simulation constitutes a cone-preserving, stochastic affine transformation on a high- dimensional population state vector indexed by age, sex, marital status, household type, employment, and education, and that the composition of yearly operators yields a random matrix product whose top Lyapunov exponent is the stochastic counterpart of the Perron–Frobenius growth rate (Caswell, 2001; Tuljapurkar, 1997)[1, 2]. The actuarial bridge is constructed by mapping simulated survival …

An Income Subsystem As A Discrete Stochastic Leslie System: A Simulation-Based Approach, Fahd Nii Okantah Cobblah

Electronic Theses and Dissertations

This thesis formulates the household-income engine of an integrated population sim- ulator as a Discrete Stochastic Leslie System (DSLS). The nonnegative state vector nt ∈ Rk + aggregates income, savings, debt, employment, and transfers. (Here, the subscript + denotes the positive cone, i.e., vectors with nonnegative components). Annual evolution is linear in state, stochastic in coefficients: nt+1 = Ttnt + εt, with Tt : Rk + → Rk + cone-preserving. Exogenous macro drivers (inflation, employment, tax, salary inflation, mortgage) are forecast via ARIMA; forecasts multiply entries of Tt, preserving linearity in expectation while introducing realistic temporal correlation. The discrete-event implemented …

On Variations Of Isolation In Graphs, Geoffrey Boyer

All Dissertations

In 2015, Caro and Hansberg introduced a wonderful and natural generalization of the well-studied parameter of domination in graphs. For a graph $G$ and a family of graphs $\FF$, they define $S$ to be an $\FF$-isolating set if $G-N[S]$ contains no member of $\FF$ as a subgraph. The case where $\FF=\{K_1\}$ coincides with domination. The case where $\FF=\{K_2\}$ is now simply referred to as an isolating set. We strengthen known results about the isolation number of a graph, and explore variations of the parameter including the independent and total versions.

In particular for connected graphs of order $n$, a bound …

Modeling The Probability Of N Clonal Rosettes In A Bromeliaceae Genetic Individual, Erin N. Bodine, Layla K. Lammers

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.