Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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 …

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 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$.

Incremental Increases Between Successive Integers When Raised To The Nth Power, Sutton J. Olesen

Rose-Hulman Undergraduate Mathematics Journal

For thousands of years, the beautiful field of number theory has captivated mathematicians with its elegant simplicity. Positive integers continue to reveal properties and relationships that are a joy to uncover, and in this paper, we investigate a pattern involving exponents and factorials while exploring some common notations in the field of number theory. Combinatorics, the field dealing with the mathematics of counting and arranging, also holds a presence in this paper. Pascal’s Triangle–the foundation of binomial expressions, also comes into play due to its tight relationship with combinatorics. Pascal’s Identity, the property that builds the triangle, becomes very useful …

Corrigendum To "Face-Magic Labelings Of Polygonal Graphs", Wai Chee Shiu, Richard M. Low, Andy K. Liu

Theory & Applications of Graphs

In this note, we correct a misstatement of a theorem.

Degeneracies Of Triangulated Graphs, Allan Bickle

Theory & Applications of Graphs

A graph $G$ is $k$-degenerate if each subgraph has minimum degree

at most $k$. The degeneracy\textbf{ }$D\left(G\right)$ is the smallest

$k$ such that $G$ is $k$-degenerate. We determine the truth values

of four statements (using different quantifiers) about when a planar

graph $G$ with degeneracy $k$ has a triangulation with degeneracy

$l$. We characterize which 3-connected planar graphs can only be

triangulated to degeneracy 3. Then we consider analogous questions

for maximal planar bipartite graphs. We prove some structural results

on these graphs, including results on decomposition of planar graphs

into various types of bipartite graphs.

Numerical Results Of New And Modified Heuristics For The Vertex Coloring Problem, Elliot Hanson

Summer Research Showcase

The chromatic number, χ(G) of an undirected graph G=(V,E) is the minimum number of colors required to color its vertices so that no two adjacent vertices have the same color. Given a graph, G, finding its chromatic number is useful for solving scheduling problems and other combinatorial optimization problems. However, determining the chromatic number of a connected graph is NP-Hard, meaning there is no known polynomial time algorithm which solves it. Thus, we are interested in heuristic solutions which give approximations for the chromatic number in polynomial time. There are well-known heuristics for finding χ(G) for any graph G. …

Skolem Number Of Kagome Lattice Graphs, Braxton Carrigan, Max Martone

Theory & Applications of Graphs

A proper Skolem labelling of a graph $G$ is a function assigning a positive integer to each vertex of $G$ such that any two vertices assigned the same integer are that distance apart in the graph. The Skolem number of a graph is smallest number $n$ such that there exists a proper Skolem labelling only using the positive integers less than or equal to $n$. In this paper, we will begin by proving the Skolem number for another family of subgraphs of the hexagonal lattice and then prove the Skolem number for two families of subgraphs of the Kagome Lattice.