Discrete Mathematics and Combinatorics Commons^™

Lattice Minors And Eulerian Posets, William Gustafson

Theses and Dissertations--Mathematics

We study a partial ordering on pairings called the uncrossing poset, which first appeared in the literature in connection with a certain stratified space of planar electrical networks. We begin by examining some of the relationships between the uncrossing poset and Catalan combinatorics, and then proceed to study the structure of lower intervals. We characterize the lower intervals in the uncrossing poset that are isomorphic to the face lattice of a cube. Moving up in complexity certain lower intervals are isomorphic to the poset of simple vertex labeled minors of an associated graph.

Inspired by this structure, we define a …

Q-Polymatroids And Their Application To Rank-Metric Codes., Benjamin Jany

Theses and Dissertations--Mathematics

Matroid theory was first introduced to generalize the notion of linear independence. Since its introduction, the theory has found many applications in various areas of mathematics including coding theory. In recent years, q-matroids, the q-analogue of matroids, were reintroduced and found to be closely related to the theory of linear vector rank metric codes. This relation was then generalized to q-polymatroids and linear matrix rank metric codes. This dissertation aims at developing the theory of q-(poly)matroid and its relation to the theory of rank metric codes. In a first part, we recall and establish preliminary results for both q-polymatroids and …

Surjectivity Of The Wahl Map On Cubic Graphs, Angela C. Hanson

Theses and Dissertations--Mathematics

Much of algebraic geometry is the study of curves. One tool we use to study curves is whether they can be embedded in a K3 surface or not. If the Wahl map is surjective on a curve, that curve cannot be embedded in a K3 surface. Therefore, studying if the Wahl map is surjective for a particular curve gives us more insight into the properties of that curve. We simplify this problem by converting graph curves to dual graphs. Then the information for graphs can be used to study the underlying curves. We will discuss conditions for the Wahl map …

Geometry Of Pipe Dream Complexes, Benjamin Reese

Theses and Dissertations--Mathematics

In this dissertation we study the geometry of pipe dream complexes with the goal of gaining a deeper understanding of Schubert polynomials. Given a pipe dream complex PD(w) for w a permutation in the symmetric group, we show its boundary is Whitney stratified by the set of all pipe dream complexes PD(v) where v > w in the strong Bruhat order. For permutations w in the symmetric group on n elements, we introduce the pipe dream complex poset P(n). The dual of this graded poset naturally corresponds to the poset of strata associated to the Whitney stratification of the boundary of …

The Explorer–Director Game On Graphs, Pat Devlin, E. Meger, A. Raz, Polymath Reu Participants

Mathematics & Statistics Faculty Works

The Explorer-Director game, first introduced by Nedev and Muthukrishnan, can be described as a game where two players—Explorer and Director—determine the movement of a token that is positioned on the vertices of some given graph. At each time step, the Explorer specifies a distance that the token must move with an aim to maximize the total number of vertices ultimately visited. However, the Director adversarially chooses where to move token in an effort to minimize this number. The game ends when no new vertices can be visited. Given a graph G and a starting vertex v, the number of vertices …

Generalized Far-Difference Representations, Prakod Ngamlamai

HMC Senior Theses

Integers are often represented as a base-$b$ representation by the sum $\sum c_ib^i$. Lekkerkerker and Zeckendorf later provided the rules for representing integers as the sum of Fibonacci numbers. Hannah Alpert then introduced the far-difference representation by providing rules for writing an integer with both positive and negative multiples of Fibonacci numbers. Our work aims to generalize her work to a broader family of linear recurrences. To do so, we describe desired properties of the representations, such as lexicographic ordering, and provide a family of algorithms for each linear recurrence that generate unique representations for any integer. We then prove …

Permutations, Representations, And Partition Algebras: A Random Walk Through Algebraic Statistics, Ian Shors

HMC Senior Theses

My thesis examines a class of functions on the symmetric group called permutation statistics using tools from representation theory. In 2014, Axel Hultman gave formulas for computing expected values of permutation statistics sampled via random walks. I present analogous formulas for computing variances of these statistics involving Kronecker coefficients – certain numbers that arise in the representation theory of the symmetric group. I also explore deep connections between the study of moments of permutation statistics and the representation theory of the partition algebras, a family of algebras introduced by Paul Martin in 1991. By harnessing these partition algebras, I derive …

On Prime Labelings Of Uniform Cycle Snake Graphs, M. A. Ollis

Emerson Authors, Researchers, & Creators

A reseaech paper in graph theory, a subfield of math. At the time of the research Agam Bedi and Samiksha Ramesh were undergraduate students at Emerson College and the work was completed as part of the SOC320 Research Co-Curricular in the summer of 2022. The work has a Creative Commons BY-NC licence.

Cayley Map Embeddings Of Complete Graphs With Even Order, Michael O'Connor

Honors Program Theses

German mathematician Claus Michael Ringel used voltage graphs to embed complete graphs onto orientable surfaces such that none of the graph's edges cross each other. Cayley maps do the same whilst being simpler to work with. The goal is to determine the efficiency of Cayley maps in embedding complete graphs onto orientable surfaces. This article focus on complete graphs of even order with an emphasis on graphs whose orders are congruent to 6 modulo 12 and 0 modulo 12. We establish 12 distinct classes that each have their own unique qualities. Through the generalization of a previous technique, we prove …

Partially Filled Latin Squares, Mariam Abu-Adas

Scripps Senior Theses

In this thesis, we analyze various types of Latin squares, their solvability and embeddings. We examine the results by M. Hall, P. Hall, Ryser and Evans first, and apply our understandings to develop an algorithm that the determines the minimum possible embedding of an unsolvable Latin square. We also study Latin squares with missing diagonals in detail.

Counting Spanning Trees On Triangular Lattices, Angie Wang

CMC Senior Theses

This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …

Investigations In The Semi-Strong Product Of Graphs And Bootstrap Percolation, Kevin J. Mccall

Theses and Dissertations

The semi-strong product of graphs G and H is a way of forming a new graph from the graphs G and H. The vertex set of the semi-strong product is the Cartesian product of the vertex sets of G and H, V(G) x V(H). The edges of the semi-strong product are determined as follows: (g₁,h₁)(g₂,h₂) is an edge of the product whenever g₁g₂ is an edge of G and h₁h₂ is an edge of H or g₁ = g₂ and h₁h_{2 …}

Strong Homotopy Lie Algebras And Hypergraphs, Samuel J. Bevins, Marco Aldi

UROP Posters

We study hypergraphs by attaching a nilpotent strong homotopy Lie algebra. We especially focus on hypergraph theoretic information that is encoded in the cohomology of the resulting strong homotopy Lie algebra.

Opposite Trees, Theo Goossens

Theses and Dissertations (Comprehensive)

A spanning tree of a graph G is a connected acyclic subgraph of G that includes all of the vertices in G. The degree of a vertex is the number of edges incident to that vertex. Given a spanning tree T of a graph G, an opposite tree of T is a spanning tree of G where the degree of each of its vertices is different from its degree in T. For complete, complete bipartite, and complete multipartite graphs, we give the conditions spanning trees of these graphs must satisfy in order to have an opposite tree.

On The Uniqueness Of Continuation Of A Partially Defined Metric, Evgeniy Petrov

Theory & Applications of Graphs

The problem of continuation of a partially defined metric can be efficiently studied using graph theory. Let G=G(V,E) be an undirected graph with the set of vertices V and the set of edges E. A necessary and sufficient condition under which the weight w : E → R⁺ on the graph G has a unique continuation to a metric d : V x V → R⁺ is found.

On Rainbow Cycles And Proper Edge Colorings Of Generalized Polygons, Matt Noble

Theory & Applications of Graphs

An edge coloring of a simple graph G is said to be proper rainbow-cycle-forbidding (PRCF, for short) if no two incident edges receive the same color and for any cycle in G, at least two edges of that cycle receive the same color. A graph G is defined to be PRCF-good if it admits a PRCF edge coloring, and G is deemed PRCF-bad otherwise. In recent work, Hoffman, et al. study PRCF edge colorings and find many examples of PRCF-bad graphs having girth less than or equal to 4. They then ask whether such graphs exist having girth greater than …

The Multiset Partition Algebra: Diagram-Like Bases And Representations, Alexander N. Wilson

Dartmouth College Ph.D Dissertations

There is a classical connection between the representation theory of the symmetric group and the general linear group called Schur--Weyl Duality. Variations on this principle yield analogous connections between the symmetric group and other objects such as the partition algebra and more recently the multiset partition algebra. The partition algebra has a well-known basis indexed by graph-theoretic diagrams which allows the multiplication in the algebra to be understood visually as combinations of these diagrams. My thesis begins with a construction of an analogous basis for the multiset partition algebra. It continues with applications of this basis to constructing the irreducible …

The Lie Algebra Sl2(C) And Krawtchouk Polynomials, Nkosi Alexander

UNF Graduate Theses and Dissertations

The Lie algebra L = sl2(C) consists of the 2 × 2 complex matrices that have trace zero, together with the Lie bracket [y, z] = yz − zy. In this thesis we study a relationship between L and Krawtchouk polynomials. We consider a type of element in L said to be normalized semisimple. Let a, a^∗ be normalized semisimple elements that generate L. We show that a, a^∗ satisfy a pair of relations, called the Askey-Wilson relations. For a positive integer N, we consider an (N + 1)-dimensional irreducible L-module V consisting of the homogeneous polynomials in two variables …

Modeling Repairable System Failure Data Using Nhpp Reliability Growth Mode., Eunice Ofori-Addo

EWU Masters Thesis Collection

Stochastic point processes have been widely used to describe the behaviour of repairable systems. The Crow nonhomogeneous Poisson process (NHPP) often known as the Power Law model is regarded as one of the best models for repairable systems. The goodness-of-fit test rejects the intensity function of the power law model, and so the log-linear model was fitted and tested for goodness-of-fit. The Weibull Time to Failure recurrent neural network (WTTE-RNN) framework, a probabilistic deep learning model for failure data, is also explored. However, we find that the WTTE-RNN framework is only appropriate failure data with independent and identically distributed interarrival …

On Eulerian Subgraphs And Hamiltonian Line Graphs, Yikang Xie

Graduate Theses, Dissertations, and Problem Reports (ETD)

A graph {\color{black}$G$} is Hamilton-connected if for any pair of distinct vertices {\color{black}$u, v \in V(G)$}, {\color{black}$G$} has a spanning $(u,v)$-path; {\color{black}$G$} is 1-hamiltonian if for any vertex subset $S \subseteq {\color{black}V(G)}$ with $|S| \le 1$, $G - S$ has a spanning cycle. Let $\delta(G)$, $\alpha'(G)$ and $L(G)$ denote the minimum degree, the matching number and the line graph of a graph $G$, respectively. The following result is obtained. {\color{black} Let $G$ be a simple graph} with $|E(G)| \ge 3$. If $\delta(G) \geq \alpha'(G)$, then each of the following holds. \\ (i) $L(G)$ is Hamilton-connected if and only if $\kappa(L(G))\ge …