Discrete Mathematics and Combinatorics Commons^™

A Stronger Strong Schottky Lemma For Euclidean Buildings, Michael E. Ferguson

Dissertations, Theses, and Capstone Projects

We provide a criterion for two hyperbolic isometries of a Euclidean building to generate a free group of rank two. In particular, we extend the application of a Strong Schottky Lemma to buildings given by Alperin, Farb and Noskov. We then use this extension to obtain an infinite family of matrices that generate a free group of rank two. In doing so, we also introduce an algorithm that terminates in finite time if the lemma is applicable for pairs of certain kinds of matrices acting on the Euclidean building for the special linear group over certain discretely valued fields.

Counting Power Domination Sets In Complete M-Ary Trees, Hays Whitlatch, Katharine Shultis, Olivia Ramirez, Michele Ortiz, Sviatlana Kniahnitskaya

Theory & Applications of Graphs

Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this paper we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time.

Hs-Integral And Eisenstein Integral Mixed Circulant Graphs, Monu Kadyan, Bikash Bhattacharjya

Theory & Applications of Graphs

A mixed graph is called second kind hermitian integral (HS-integral) if the eigenvalues of its Hermitian-adjacency matrix of the second kind are integers. A mixed graph is called Eisenstein integral if the eigenvalues of its (0, 1)-adjacency matrix are Eisenstein integers. We characterize the set S for which a mixed circulant graph Circ(Z_n, S) is HS-integral. We also show that a mixed circulant graph is Eisenstein integral if and only if it is HS-integral. Further, we express the eigenvalues and the HS-eigenvalues of unitary oriented circulant graphs in terms of generalized Möbius function.

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.

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.

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 …

Kōlams In Graph Theory: Mathematics In South Indian Ritual Art, Nathan Hartmann

Murray State Theses and Dissertations

Kōlams are a ritual art form found in India, most commonly in the southern state
of Tamil Nadu. Comprised of different interlocking knots, these women-drawn designs are placed on the entrances to people’s home to showcase the household’s emotional state and ask the earth goddess Bhūdevi for forgiveness. More aesthetically pleasing kōlams are considered latshanam, where the design permeates beauty; monolinearity is one such aspect that implements latshanam. Using graph theory, we examine one style of these drawings, the labyrinthine variety, to identify if a given kōlam is monolinear and how to construct monolinear kōlams.

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 …}

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 …