Discrete Mathematics and Combinatorics Commons^™

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

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

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 …

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 …

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 …

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 …

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 …

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 …

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

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 …

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 …

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.

Forbidden Triples For $2$-Connected Graphs With Minimum Degree Three Which Contain $K_4$ And $K_{2,2}$, Takafumi Kotani, Yoshimi Egawa

Theory & Applications of Graphs

For a family $\mathcal{H}$ of graphs, a graph $G$ is said to be $\mathcal{H}$-free if $G$ contains no member of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{G}_2^{(3)}}(\mathcal{H})$ denote the family of $2$-connected $\mathcal{H}$-free graphs having minimum degree at least $3$. This paper is concerned with families $\mathcal{H}$ of connected graphs with $|\mathcal{H}| = 3$ such that $\mathcal{G}_2^{(3)}}(\mathcal{H})$ is a finite family. In particular, we show that for a connected graph $T$ of order at least $3$ that is not a star, $\mathcal{G}_2^{(3)}(\{K_4,K_{2,2},T\})$ is finite if and only if $T$ is a path of order at most $6$.

Star-Critical Weakened Ramsey Numbers, Mark R. Budden, Monu Moun, Jagjeet Jakhar

Theory & Applications of Graphs

The weakened Ramsey number $r^{s,t}(G)$ is defined to be the least $p\in \mathbb{N}$ such that every $t$-coloring of the edges of the complete graph $K_p$ contains a subgraph isomorphic to $G$ that is spanned by edges that use at most $s$ colors ($1\le s\le t-1$). The star-critical weakened Ramsey number $r^{s,t}_*(G)$ then determines the minimum number of edges that must join a vertex to $K_{r^{s,t}(G)-1}$ in order for this Ramsey property to hold. We begin by showing that $r_*^{s,t}(K_n)=r^{s,t}(K_n)-1$ for all $n\in \mathbb{N}$. Then, building off of Khamseh and Omidi's recent determination of $r^{s,t}(K_{1,n})$ when $s=t-1$ and $s=t-2$, we focus …

Packing Independent Cliques Into Planar Graphs, Csaba Biró, Gabriel Collado, Oscar Zamora

Theory & Applications of Graphs

The indeque number of a graph is largest set of vertices that induce an independent set of cliques. We study the extremal value of this parameter for the class and subclasses of planar graphs, most notably for forests and graphs of pathwidth at most $2$.