Discrete Mathematics and Combinatorics Commons^™

The Sensitivity Of A Laplacian Family Of Ranking Methods, Claire S. Chang

HMC Senior Theses

Ranking from pairwise comparisons is a particularly rich subset of ranking problems. In this work, we focus on a family of ranking methods for pairwise comparisons which encompasses the well-known Massey, Colley, and Markov methods. We will accomplish two objectives to deepen our understanding of this family. First, we will consider its network diffusion interpretation. Second, we will analyze its sensitivity by studying the "maximal upset" where the direction of an arc between the highest and lowest ranked alternatives is flipped. Through these analyses, we will build intuition to answer the question "What are the characteristics of robust ranking methods?" …

Geometric And Combinatorial Properties Of Lattice Polytopes Defined From Graphs, Kaitlin Bruegge

Theses and Dissertations--Mathematics

Polytopes are geometric objects that generalize polygons in the plane and polyhedra in 3-dimensional space. Of particular interest in geometric combinatorics are families of lattice polytopes defined from combinatorial objects, such as graphs. In particular, this dissertation studies symmetric edge polytopes (SEPs), defined from simple undirected graphs. In 2019, Higashitani, Jochemko, and Michalek gave a combinatorial description of the hyperplanes that support facets of a symmetric edge polytope in terms of certain labelings of the underlying graph.
Using this framework, we explore the number of facets that can be attained by the symmetric edge polytopes for graphs with certain structure. …

An Inquiry Into Lorentzian Polynomials, Tomás Aguilar-Fraga

HMC Senior Theses

In combinatorics, it is often desirable to show that a sequence is unimodal. One method of establishing this is by proving the stronger yet easier-to-prove condition of being log-concave, or even ultra-log-concave. In 2019, Petter Brändén and June Huh introduced the concept of Lorentzian polynomials, an exciting new tool which can help show that ultra-log-concavity holds in specific cases. My thesis investigates these Lorentzian polynomials, asking in which situations they are broadly useful. It covers topics such as matroid theory, discrete convexity, and Mason’s conjecture, a long-standing open problem in matroid theory. In addition, we discuss interesting applications to known …

Discrete Analogues Of The Poincaré-Hopf Theorem, Kate Perkins

HMC Senior Theses

My thesis unpacks the relationship between two discrete formulations of the Poincaré-Hopf index theorem. Chapter 1 introduces necessary definitions. Chapter 2 describes the discrete analogs and their differences. Chapter 3 contains a proof that one analog implies the other and chapter 4 contains a proof that the Poincaré-Hopf theorem implies the discrete analogs. Finally, chapter 5 presents still open questions and further research directions.

Methods Of Computing Graph Gonalities, Noah Speeter

Theses and Dissertations--Mathematics

Chip firing is a category of games played on graphs. The gonality of a graph tells us how many chips are needed to win one variation of the chip firing game. The focus of this dissertation is to provide a variety of new strategies to compute the gonality of various graph families. One family of graphs which this dissertation is particularly interested in is rook graphs. Rook graphs are the Cartesian product of two or more complete graphs and we prove that the gonality of two dimensional rook graphs is the expected value of (n − 1)m where n is …

Long Increasing Subsequences, Hannah Friedman

HMC Senior Theses

In my thesis, I investigate long increasing subsequences of permutations from two angles. Motivated by studying interpretations of the longest increasing subsequence statistic across different representations of permutations, we investigate the relationship between reduced words for permutations and their RSK tableaux in Chapter 3. In Chapter 4, we use permutations with long increasing subsequences to construct a basis for the space of ��-local functions.

Quasisymmetric Functions Distinguishing Trees, Jean-Christophe Aval, Karimatou Djenabou, Peter R. W. Mcnamara

Faculty Journal Articles

A famous conjecture of Stanley states that his chromatic symmetric function distinguishes trees. As a quasisymmetric analogue, we conjecture that the chromatic quasisymmetric function of Shareshian and Wachs and of Ellzey distinguishes directed trees. This latter conjecture would be implied by an affirmative answer to a question of Hasebe and Tsujie about the P-partition enumerator distinguishing posets whose Hasse diagrams are trees. They proved the case of rooted trees and our results include a generalization of their result.

Colorful Graph Associahedra, Satyan L. Devadoss, Mia Smith

Mathematics: Faculty Scholarship

Given a graph G, the graph associahedron is a simple convex polytope whose face poset is based on the connected subgraphs of G. With the additional assignment of a color palette, we define the colorful graph associahedron, show it to be a collection of simple abstract polytopes, and explore its properties.

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 …

Selected Problems In Graph Coloring, Hudson Lafayette

Theses and Dissertations

The Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4.

For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or nearly sharp upper bounds on the t-tone chromatic number of various classes of sparse graphs. In particular, we determine τ2(G) exactly when mad(G) < 12/5 and also determine τ2(G), up to a small additive constant, when G is outerplanar. Finally, we determine τt(Cn) exactly when t ∈ {3, 4, 5}.

Rainbow Turan Methods For Trees, Victoria Bednar

Theses and Dissertations

The rainbow Turan number, a natural extension of the well-studied traditional
Turan number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstraete. The rainbow Tur ́an number of a graph F , ex*(n, F ), is the largest number of edges for an n vertex graph G that can be properly edge colored with no rainbow F subgraph. Chapter 1 of this dissertation gives relevant definitions and a brief history of extremal graph theory. Chapter 2 defines k-unique colorings and the related k-unique Turan number and provides preliminary results on this new variant. In Chapter 3, we explore the …

Minimal Sets, Union-Closed Families, And Frankl's Conjecture, Christopher S. Flippen

Theses and Dissertations

The most common statement of Frankl's conjecture is that for every finite family of sets closed under the union operation, there is some element which belongs to at least half of the sets in the family. Despite its apparent simplicity, Frankl's conjecture has remained open and highly researched since its first mention in 1979. In this paper, we begin by examining the history and previous attempts at solving the conjecture. Using these previous ideas, we introduce the concepts of minimal sets and minimally-generated families, some ideas related to viewing union-closed families as posets, and some constructions of families involving poset-defined …

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 …

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 …

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.

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 …

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 …

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.

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 …

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.

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 …