Discrete Mathematics and Combinatorics Commons^™

Finding Triangular Cayley Maps With Graph Touring, Hannah Hendrickson

Honors Program Theses

We develop a method for determining whether certain kinds of Cayley maps can exist by using multi-digraph representations of the data in the Cayley maps. Euler tours of these multi-digraphs correspond exactly to the permutations which define Cayley maps. We also begin to classify which 3-regular multi-digraphs have "non-backtracking" Euler tours in general.

Counting The Moduli Space Of Pentagons On Finite Projective Planes, Maxwell Hosler

Senior Independent Study Theses

Finite projective planes are finite incidence structures which generalize the concept of the real projective plane. In this paper, we consider structures of points embedded in these planes. In particular, we investigate pentagons in general position, meaning no three vertices are colinear. We are interested in properties of these pentagons that are preserved by collineation of the plane, and so can be conceived as properties of the equivalence class of polygons up to collineation as a whole. Amongst these are the symmetries of a pentagon and the periodicity of the pentagon under the pentagram map, and a generalization of …

On The Polytopal Generalization Of Sperner’S Lemma, Amit Harlev

HMC Senior Theses

We introduce and prove Sperner’s lemma, the well known combinatorial analogue of the Brouwer fixed point theorem, and then attempt to gain a better understanding of the polytopal generalization of Sperner’s lemma conjectured in Atanassov (1996) and proven in De Loera et al. (2002). After explaining the polytopal generalization and providing examples, we present a new, simpler proof of a slightly weaker result that helps us better understand the result and why it is correct. Some ideas for how to generalize this proof to the complete result are discussed. In the last two chapters we provide a brief introduction to …

Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi

HMC Senior Theses

In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in 𝐏 are thought of as 0-turn games, 𝐍𝐏 as 1-turn “puzzle” games, and in general 𝚺ₖ𝐏 as 𝑘-turn games, in which decision problems answer the binary question, “can the starting player guarantee a win?” We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of 𝑘-turn CIRCUIT SATISFIABILITY games, whose 𝚺ₖ𝐏-completeness is assumed from prior work (we briefly justify this assumption …

Combinatorial Optimization With Photonics-Inspired Clock Models, Mostafa Honari-Latifpour, Matthew S. Mills, Mohammad-Ali Miri

Publications and Research

NP-hard combinatorial optimization problems are in general hard problems that their computational complexity grows faster than polynomial scaling with the size of the problem. Thus, over the years there has been a great interest in developing unconventional methods and algorithms for solving such problems. Here, inspired by the nonlinear optical process of q-photon down-conversion, in which a photon is converted into q degenerate lower energy photons, we introduce a nonlinear dynamical model that builds on coupled single-variable phase oscillators and allows for efficiently approximating the ground state of the classical q-state planar Potts Hamiltonian. This reduces the exhaustive search in …

Geometric Properties Of Weighted Projective Space Simplices, Derek Hanely

Theses and Dissertations--Mathematics

A long-standing conjecture in geometric combinatorics entails the interplay between three properties of lattice polytopes: reflexivity, the integer decomposition property (IDP), and the unimodality of Ehrhart h*-vectors. Motivated by this conjecture, this dissertation explores geometric properties of weighted projective space simplices, a class of lattice simplices related to weighted projective spaces.

In the first part of this dissertation, we are interested in which IDP reflexive lattice polytopes admit regular unimodular triangulations. Let Delta_(1,q)denote the simplex corresponding to the associated weighted projective space whose weights are given by the vector (1,q). Focusing on the case where Delta …

On Flow Polytopes, Nu-Associahedra, And The Subdivision Algebra, Matias Von Bell

Theses and Dissertations--Mathematics

This dissertation studies the geometry and combinatorics related to a flow polytope F_car(ν) constructed from a lattice path ν, whose volume is given by the ν-Catalan numbers. It begins with a study of the ν-associahedron introduced by Ceballos, Padrol, and Sarmiento in 2019, but from the perspective of Schröder combinatorics. Some classical results for Schröder paths are extended to the ν-setting, and insights into the geometry of the ν-associahedron are obtained by describing its face poset with two ν-Schröder objects. The ν-associahedron is then shown to be dual to a framed triangulation of F_car(ν), which is a …

Stroke Clustering And Fitting In Vector Art, Khandokar Shakib

Senior Independent Study Theses

Vectorization of art involves turning free-hand drawings into vector graphics that can be further scaled and manipulated. In this paper, we explore the concept of vectorization of line drawings and study multiple approaches that attempt to achieve this in the most accurate way possible. We utilize a software called StrokeStrip to discuss the different mathematics behind the parameterization and fitting involved in the drawings.

Dot Product Bounds In Galois Rings, David Lee Crosby

MSU Graduate Theses

We consider the Erdős Distance Conjecture in the context of dot products in Galois rings and prove results for single dot products and pairs of dot products.

Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer

Theses and Dissertations--Computer Science

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a …

Automated Conjecturing On The Independence Number And Minimum Degree Of Diameter-2-Critical Graphs, Joshua R. Forkin

Theses and Dissertations

A diameter-2-critical (D2C) graph is a graph with diameter two such that removing any edge increases the diameter or disconnects the graph. In this paper, we look at other lesser-studied properties of D2C graphs, focusing mainly on their independence number and minimum degree. We show that there exist D2C graphs with minimum degree strictly larger than their independence number, and that this gap can be arbitrarily large. We also exhibit D2C graphs with maximum number of common neighbors strictly greater than their independence number, and that this gap can be arbitrarily large. Furthermore, we exhibit a D2C graph whose number …

Multicolor Ramsey And List Ramsey Numbers For Double Stars, Jake Ruotolo

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For a graph H, the k-color Ramsey number r(H; k) of H is the smallest integer n such that every k-edge-coloring of K_n contains a monochromatic copy of H. Despite active research for decades, very little is known about Ramsey numbers of graphs. This is especially true for r(H; k) when k is at least 3, also known as the multicolor Ramsey number of …

Equitable Coloring Of Complete Tripartitle Graphs, Maxwell Vlam, Bailey Orehosky, Dominic Ditizio

Capstone Showcase

In this paper, we prove the Equitable Coloring Conjecture for variations of complete tripartite graphs with graphs K_n,n,n, K_n,n,2n, K_n,n,n+2, and K_n,n+2,n+4.

Polychromatic Colorings Of Certain Subgraphs Of Complete Graphs And Maximum Densities Of Substructures Of A Hypercube, Ryan Tyler Hansen

Graduate Theses, Dissertations, and Problem Reports

If G is a graph and H is a set of subgraphs of G, an edge-coloring of G is H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, poly_HG, is the largest number of colors in an H-polychromatic coloring. We determine poly_HG exactly when G is a complete graph on n vertices, q a fixed nonnegative integer, and H is the family of one of: all matchings spanning n-q vertices, all 2-regular graphs spanning at least n-q vertices, or all cycles of length precisely n-q. …

On Generalizations Of Supereulerian Graphs, Sulin Song

Graduate Theses, Dissertations, and Problem Reports

A graph is supereulerian if it has a spanning closed trail. Pulleyblank in 1979 showed that determining whether a graph is supereulerian, even when restricted to planar graphs, is NP-complete. Let $\kappa'(G)$ and $\delta(G)$ be the edge-connectivity and the minimum degree of a graph $G$, respectively. For integers $s \ge 0$ and $t \ge 0$, a graph $G$ is $(s,t)$-supereulerian if for any disjoint edge sets $X, Y \subseteq E(G)$ with $|X|\le s$ and $|Y|\le t$, $G$ has a spanning closed trail that contains $X$ and avoids $Y$. This dissertation is devoted to providing some results on $(s,t)$-supereulerian graphs and …

Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler

Graduate Student Theses, Dissertations, & Professional Papers

In this study we present a novel algorithm, LASSO, for solving the unbounded and bounded subset sum problem. The LASSO algorithm was designed to solve the unbounded SSP quickly and to return all subsets summing to a target sum. As speed was the highest priority, we benchmarked the run time performance of LASSO against implementations of some common approaches to the bounded SSP, as well as the only comparable implementation for solving the unbounded SSP that we could find. In solving the bounded SSP, our algorithm had a significantly faster run time than the competing algorithms when the target sum …