Digital Commons Network^™

The Fundamental Groupoid In Discrete Homotopy Theory, Udit Ajit Mavinkurve

Electronic Thesis and Dissertation Repository

Discrete homotopy theory is a homotopy theory designed for studying graphs and for detecting combinatorial, rather than topological, “holes”. Central to this theory are the discrete homotopy groups, defined using maps out of grids of suitable dimensions. Of these, the discrete fundamental group in particular has found applications in various areas of mathematics, including matroid theory, subspace arrangements, and topological data analysis.

In this thesis, we introduce the discrete fundamental groupoid, a multi-object generalization of the discrete fundamental group, and use it as a starting point to develop some robust computational techniques. A new notion of covering graphs allows us …

Cohen-Macaulay Type Of Open Neighborhood Ideals Of Unmixed Trees, Jounglag Lim

All Theses

Given a tree T and a field k, we define the open neighborhood ideal N(T) of T in k[V] to be the ideal generated by the open neighborhoods of all vertices in the graph. If T is unmixed with respect to the total domination problem, then it is known that N(T) is Cohen-Macaulay. Our goal is to compute the (Cohen-Macaulay) type of k[V]/N(T) using graph theoretical properties of T. We achieve this by using homological algebra and properties of monomial ideals. Along the way, we also provide a different characterization of unmixed trees and a generalization of the total dominating …

Penney’S Game For Permutations, Yixin Lin

Dartmouth College Ph.D Dissertations

We explore the permutation analog of Penney's game for coin flips. Two players, in order, each choose a permutation of length $k\ge3$. Then a sequence of independent random values from a continuous distribution is generated until the relative order of the last $k$ numbers matches one of the chosen permutations, declaring the player who selected that permutation as the winner.

We calculate the winning probabilities for all pairs of permutations of length $3$ and some pairs of length $4$, demonstrating the non-transitive property of this game, consistent with the original word version. Alternatively, we provide formulas for computing the winning …

On Pattern Avoidance And Dynamical Algebraic Combinatorics, Benjamin Adenbaum

Dartmouth College Ph.D Dissertations

Over the past decade since the term `dynamical algebraic combinatorics' was coined there has been a tremendous amount of activity in the field. Adding to that growing body of work this thesis hopes to be a step towards a broader study of pattern avoidance within dynamical algebraic combinatorics and helps initiate that by considering an action of rowmotion on 321-avoiding permutations. Additionally within we show the first known instance of piecewise-linear rowmotion periodicity for an infinite family of posets that does not follow from a more general birational result. Finally we show that the code of permutation restricted to permutations …

Boolean Group Structure In Class Groups Of Positive Definite Quadratic Forms Of Primitive Discriminant, Christopher Albert Hudert Jr.

Student Research Submissions

It is possible to completely describe the representation of any integer by binary quadratic forms of a given discriminant when the discriminant’s class group is a Boolean group (also known as an elementary abelian 2-group). For other discriminants, we can partially describe the representation using the structure of the class group. The goal of the present project is to find whether any class group with 32 elements and a primitive positive definite discriminant is a Boolean group. We find that no such class group is Boolean.

An Alternate Proof For The Top-Heavy Conjecture On Partition Lattices Using Shellability, Brian Macdonald, Josh Hallam

Honors Thesis

A partially ordered set, or poset, is governed by an ordering that may or may not relate
any pair of objects in the set. Both the bonds of a graph and the partitions of a set are
partially ordered, and their poset structure can be depicted visually in a Hasse diagram. The
partitions of {1, 2, ..., n} form a particularly important poset known as the partition lattice
Πn. It is isomorphic to the bond lattice of the complete graph Kn, making it a special case
of the family of bond lattices.
Dowling and Wilson’s 1975 Top-Heavy Conjecture states that …

Domination In Graphs And The Removal Of A Matching, Geoffrey Boyer

All Theses

We consider how the domination number of an undirected graph changes on the removal of a maximal matching. It is straightforward that there are graphs where no matching removal increases the domination number, and where some matching removal doubles the domination number. We show that in a nontrivial tree there is always a matching removal that increases the domination number; and if a graph has domination number at least $2$ there is always a maximal matching removal that does not double the domination number. We show that these results are sharp and discuss related questions.

The Modular Generalized Springer Correspondence For The Symplectic Group, Joseph Dorta

LSU Doctoral Dissertations

The Modular Generalized Springer Correspondence (MGSC), as developed by Achar, Juteau, Henderson, and Riche, stands as a significant extension of the early groundwork laid by Lusztig's Springer Correspondence in characteristic zero which provided crucial insights into the representation theory of finite groups of Lie type. Building upon Lusztig's work, a generalized version of the Springer Correspondence was later formulated to encompass broader contexts.

In the realm of modular representation theory, Juteau's efforts gave rise to the Modular Springer Correspondence, offering a framework to explore the interplay between algebraic geometry and representation theory in positive characteristic. Achar, Juteau, Henderson, and Riche …

On Generating Bijections For Permutations And Inversion Sequences, Melanie J. Ferreri

Dartmouth College Ph.D Dissertations

Given an algebraic proof of a combinatorial identity, we use recursive methods to construct a bijection demonstrating the identity.

Our first application centers around derangements and nonderangements. A derangement is a permutation with no fixed point, and a nonderangement is a permutation with at least one fixed point. There is a one-term recurrence for the number of derangements of n elements, and we describe a bijective proof of this recurrence which can be found using a recursive map. We then show the combinatorial interpretation of this bijection and how it compares with other known bijections, and show how this extends …

Counting Conjugates Of Colored Compositions, Jesus Omar Sistos Barron

Honors College Theses

The properties of n-color compositions have been studied parallel to those of regular compositions. The conjugate of a composition as defined by MacMahon, however, does not translate well to n-color compositions, and there is currently no established analogous concept. We propose a conjugation rule for cyclic n-color compositions. We also count the number of self-conjugates under these rules and establish a couple of connections between these and regular compositions.

Symmetry And Structures Of Apn Functions And Sidon Sets, Darrion Thornburgh

Senior Projects Spring 2024

Let $\mathbb{F}_p^n$ be the $n$-dimensional vector space over $\mathbb{F}_p$. The graph $\mathcal{G}_F = \{ (x, F(x)) : x \in \mathbb{F}_p^n \}$ of a vectorial function $F \colon \mathbb{F}_p^n \to \mathbb{F}_p^m$ can have interesting combinatorial properties depending on varying cryptographic conditions on $F$. A vectorial Boolean function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ is almost perfect nonlinear (APN) if there are at most $2$ solutions to the equation $F(x+a) + F(x) = b$ for all $a,b \in \mathbb{F}_2^n$ where $a \neq 0$. Equivalently, $F$ is APN if and only if $\mathcal{G}_F$ is a Sidon set, that is, a set in $\mathbb{F}_2^n$ where …

Folding And Embedding Cubical Complexes, Skye Rothstein

Senior Projects Spring 2024

Senior Project submitted to The Division of Science, Mathematics and Computing of Bard College.

In this project we study the folding properties of several special classes of cubical complexes. First, we look at polyominoids, which are arrangements of congruent squares in 3-space, glued edge-to-edge at 90° and 180° angles. We construct and analyze the mechanical configuration space for n-cell polyominoids, which is a graph with vertex set given by all n-cell polyominoids, where two vertices are connected by an edge if you can transform one into the other by one hinge movement. For n = 4, we provide a complete …

Problems In Chemical Graph Theory Related To The Merrifield-Simmons And Hosoya Topological Indices, William B. O'Reilly

Electronic Theses and Dissertations

In some sense, chemical graph theory applies graph theory to various physical sciences. This interdisciplinary field has significant applications to structure property relationships, as well as mathematical modeling. In particular, we focus on two important indices widely used in chemical graph theory, the Merrifield-Simmons index and Hosoya index. The Merrifield-Simmons index and the Hosoya index are two well-known topological indices used in mathematical chemistry for characterizing specific properties of chemical compounds. Substantial research has been done on the two indices in terms of enumerative problems and extremal questions. In this thesis, we survey known extremal results and consider the generalized …

On Graph Decompositions And Designs: Exploring The Hamilton-Waterloo Problem With A Factor Of 6-Cycles And Projective Planes Of Order 16, Zazil Santizo Huerta

Dissertations, Master's Theses and Master's Reports

This dissertation tackles the challenging graph decomposition problem of finding solutions to the uniform case of the Hamilton-Waterloo Problem (HWP). The HWP seeks decompositions of complete graphs into cycles of specific lengths. Here, we focus on cases with a single factor of 6-cycles. The dissertation then delves into the construction of 1-rotational designs, a concept from finite geometry. It explores the connection between these designs and finite projective planes, which are specific geometric structures. Finally, the dissertation proposes a potential link between these seemingly separate areas. It suggests investigating whether 1-rotational designs might hold the key to solving unsolved instances …

Slₖ-Tilings And Paths In ℤᵏ, Zachery T. Peterson

Theses and Dissertations--Mathematics

An SLₖ-frieze is a bi-infinite array of integers where adjacent entries satisfy a certain diamond rule. SL₂-friezes were introduced and studied by Conway and Coxeter. Later, these were generalized to infinite matrix-like structures called tilings as well as higher values of k. A recent paper by Short showed a bijection between bi-infinite paths of reduced rationals in the Farey graph and SL₂-tilings. We extend this result to higher k by constructing a bijection between SLₖ-tilings and certain pairs of bi-infinite strips of vectors in ℤᵏ called paths. The key ingredient in the proof is the relation to Plucker friezes and …

Paley Graphs, Prime Graphs, And Crossword Puzzles, Robert D. Jacobs Jr.

Theses and Dissertations

In this paper, we will talk about many different mathematical concepts. We will prove theorems about Paley graphs, prime graphs, and crossword puzzles. It will be very fun.

The results in the section about Paley graphs include structure theorems about the subgraph induced by the quadratic residues, the subgraph induced by the non-residues and a few related subgraphs. The main is to better understand the “independence structure” of the Paley graph itself. No good upper bound on the independence number of Paley graphs is known. Theorems about these subgraphs, and various counts aim at future improvement of upper bounds for …

Graph Coloring Reconfiguration, Reem Mahmoud

Theses and Dissertations

Reconfiguration is the concept of moving between different solutions to a problem by transforming one solution into another using some prescribed transformation rule (move). Given two solutions s₁ and s₂ of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s₁ into s₂. Reconfiguration is an area of research with many contributions towards various fields such as mathematics and computer science.
The k-coloring reconfiguration problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type …

Enumeration Of Lattice Paths With Restrictions, Vince White

Electronic Theses and Dissertations

Lattice path enumeration, through the lens of Catalan numbers, plays a crucial role in combinatorics. This thesis delves into enumerations of some of the most common lattice paths – north-east paths, up-down paths, and Dyck paths – with restrictions applied. The first restriction is counting north-east lattice paths that only cross the diagonal line, y=x, once. The second form of lattice paths with restrictions is up-down paths that cross the x-axis exactly once and fall to a fixed depth of k. While working through this module, a novel proof for a known integer sequence was used, then applied to generate …

The Dual Boundary Complex Of The Moduli Space Of Cyclic Compactifications, Toby Anderson

HMC Senior Theses

Moduli spaces provide a useful method for studying families of mathematical objects. We study certain moduli spaces of algebraic curves, which are generalizations of familiar lines and conics. This thesis focuses on, Δ^(r,n), the dual boundary complex of the moduli space of genus-zero cyclic curves. This complex is itself a moduli space of graphs and can be investigated with combinatorial methods. Remarkably, the combinatorics of this complex provides insight into the geometry and topology of the original moduli space. In this thesis, we investigate two topologically invariant properties of Δ^(r,n). We compute its Euler characteristic and …

A Combinatorial Model For Affine Demazure Crystals Of Levels Zero And One, Samuel Spellman

Electronic Theses & Dissertations (2024 - present)

The symmetric and non-symmetric Macdonald polynomials are special families of orthogonal polynomials with parameters q and t. They are indexed by dominant, (resp. arbitrary) weights associated to a root system and generalize several well-known polynomials such as the Schur polynomials, Jack polynomials, Hall-Littlewood polynomials, etc. There are two well-known combinatorial models for computing these polynomials: a tableau model in type A, due to Haglund, Haiman and Loehr, and a type-independent model due to Ram and Yip, based on alcove walks.

Crystals bases are an important construction encoding information about Lie algebra representations. It turns out that there is an interesting …

An Unsupervised Machine Learning Algorithm For Clustering Low Dimensional Data Points In Euclidean Grid Space, Josef Lazar

Senior Projects Spring 2024

Clustering algorithms provide a useful method for classifying data. The majority of well known clustering algorithms are designed to find globular clusters, however this is not always desirable. In this senior project I present a new clustering algorithm, GBCN (Grid Box Clustering with Noise), which applies a box grid to points in Euclidean space to identify areas of high point density. Points within the grid space that are in adjacent boxes are classified into the same cluster. Conversely, if a path from one point to another can only be completed by traversing an empty grid box, then they are classified …

Solid Angle Measure Approximation Methods For Polyhedral Cones, Allison Fitisone

Theses and Dissertations--Mathematics

Polyhedral cones are of interest in many fields, like geometry and optimization. A simple, yet fundamental question we may ask about a cone is how large it is. As cones are unbounded, we consider their solid angle measure: the proportion of space that they occupy. Beyond dimension three, definitive formulas for this measure are unknown. Consequently, devising methods to estimate this quantity is imperative. In this dissertation, we endeavor to enhance our understanding of solid angle measures and provide valuable insights into the efficacy of various approximation techniques.

Ribando and Aomoto independently discovered a Taylor series formula for solid angle …

Results On $K$-Covers In The Game Quads, Daniel Melvin Rose-Levine

Senior Projects Spring 2024

This project explores the $k$-cover conjecture for the game Quads. The conjecture states that for all $k\in\mathbb{N}$, there exists a $k$-cover if and only if $k = 2$ or $k = \frac{2^n-2}{6}$ for some odd $n\in\mathbb{N}$ with $n>1$. We show that if $k$ is one of these values, then there exists a $k$-cover. We discuss partial results in the other direction, i.e., that these are the only values of $k$ for which there exists a $k$-cover.

Problems In Graph Theory With Applications To Topology And Modeling Rna, Rayan K. Ibrahim

Theses and Dissertations

In this thesis, we explore four projects. In the first project, we explore $r$-neighbor bootstrap percolation on a graph $G$. We establish upper bounds for the number of vertices required to percolate in the case that $r=2$ for particular classes of graphs. In the second project, we study the structure of graphs with independence number two. We prove a lower bound on the number of edges of such graphs, related to an upper bound on the number of edges in a triangle-saturated graph, and give a sufficient forbidden induced subgraph condition for independence number two graphs. In the third project, …

Zeckendorf Representation Analysis On Third Order Fibonacci Sequences That Do Not Satisfy The Uniqueness Property, Samuel A. Aguilar

Honors College Theses

Zeckendorf's Theorem states that every natural number can be expressed uniquely as the sum of distinct non-consecutive terms of the shifted Fibonacci sequence (i.e. 1, 2, 3, 5, ...). This theorem has motivated the study of representation of integers by the sum of non-adjacent terms of Nth order Fibonacci sequences, including the characterization of the uniqueness of Zeckendorf representation based on the initial terms of the sequence. Moreover, when this uniqueness property is satisfied for third order Fibonacci sequences, the ratio of integers less than a given number X that have a Zeckendorf representation has been estimated by Dr. Sungkon …

A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu

Electronic Theses and Dissertations

Graph Neural Networks and Transformers are very powerful frameworks for learning machine learning tasks. While they were evolved separately in diverse fields, current research has revealed some similarities and links between them. This work focuses on bridging the gap between GNNs and Transformers by offering a uniform framework that highlights their similarities and distinctions. We perform positional encodings and identify key properties that make the positional encodings node embeddings. We found that the properties of expressiveness, efficiency and interpretability were achieved in the process. We saw that it is possible to use positional encodings as node embeddings, which can be …

Foundations Of Memory Capacity In Models Of Neural Cognition, Chandradeep Chowdhury

Master's Theses

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the …

Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham

All Theses

Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.

Zero-Knowledge Reductions And Confidential Arithmetic, Marvin Jones

All Dissertations

The changes in computing paradigms to shift computations to third parties have resulted in the necessity of these computations to be provable. Zero-knowledge arguments are probabilistic arguments that are used to to verify computations without secret data being leaked to the verifying party.

In this dissertation, we study zero-knowledge arguments with specific focus on reductions. Our main contributions are:

1. Provide a thorough survey in a variety of zero-knowledge techniques and protocols.
2. Prove various results of reductions that can be used to study interactive protocols in terms of subroutines. Additionally, we identify an issue in the analogous definition of zero-knowledge for …

Jumping Frogs On Cyclic Graphs, Jake Mitchell

Honors College Theses

From the traditional game of Solitaire to modern video games like Candy Crush and Five Nights at Freddy’s, single-player games have captivated audiences for gener- ations. We investigate a lesser-known single-player game, the Jumping Frogs problem, on various classes of simple graphs, a graph with no multiple edges or looped ver- tices. We determine whether frogs can be stacked together on one vertex of a given graph. In a graph with k vertices and one frog on each vertex, the frogs must make legal jumps to form a stack of k frogs. The problem is known to be solvable on …