Discrete Mathematics and Combinatorics Commons^™

Uconn Baseball Batting Order Optimization, Gavin Rublewski, Gavin Rublewski

Honors Scholar Theses

Challenging conventional wisdom is at the very core of baseball analytics. Using data and statistical analysis, the sets of rules by which coaches make decisions can be justified, or possibly refuted. One of those sets of rules relates to the construction of a batting order. Through data collection, data adjustment, the construction of a baseball simulator, and the use of a Monte Carlo Simulation, I have assessed thousands of possible batting orders to determine the roster-specific strategies that lead to optimal run production for the 2023 UConn baseball team. This paper details a repeatable process in which basic player statistics …

Incorporating Perspectival Elements In A Discrete Mathematics Course, Calvin Jongsma

Faculty Work Comprehensive List

Discrete mathematics is a vast field that can be explored along many different paths. Opening with a unit on logic and proof and then taking up some additional core topics (induction, set theory, combinatorics, relations, Boolean algebra, graph theory) allows one to bring in a wealth of relevant material on history, philosophy, axiomatics, and abstraction in very natural ways. This talk looks at how my 2019 textbook on discrete mathematics, focused in this way, came to be, and it highlights the various perspectival elements the book includes.

Staircase Packings Of Integer Partitions, Melody Arteaga

Mathematics, Statistics, and Computer Science Honors Projects

An integer partition is a weakly decreasing sequence of positive integers. We study the family of packings of integer partitions in the triangular array of size n, where successive partitions in the packings are separated by at least one zero. We prove that these are enumerated by the Bell-Like number sequence (OEIS A091768), and investigate its many recursive properties. We also explore their poset (partially ordered set) structure. Finally, we characterize various subfamilies of these staircase packings, including one restriction that connects back to the original patterns of the whole family.

Mixing Measures For Trees Of Fixed Diameter, Ari Holcombe Pomerance

Mathematics, Statistics, and Computer Science Honors Projects

A mixing measure is the expected length of a random walk in a graph given a set of starting and stopping conditions. We determine the tree structures of order n with diameter d that minimize and maximize for a few mixing measures. We show that the maximizing tree is usually a broom graph or a double broom graph and that the minimizing tree is usually a seesaw graph or a double seesaw graph.

Reverse Mathematics Of Ramsey's Theorem, Nikolay Maslov

Electronic Theses, Projects, and Dissertations

Reverse mathematics aims to determine which set theoretic axioms are necessary to prove the theorems outside of the set theory. Since the 1970’s, there has been an interest in applying reverse mathematics to study combinatorial principles like Ramsey’s theorem to analyze its strength and relation to other theorems. Ramsey’s theorem for pairs states that for any infinite complete graph with a finite coloring on edges, there is an infinite subset of nodes all of whose edges share one color. In this thesis, we introduce the fundamental terminology and techniques for reverse mathematics, and demonstrate their use in proving Kőnig's lemma …

Roots Of Quaternionic Polynomials And Automorphisms Of Roots, Olalekan Ogunmefun

Electronic Theses and Dissertations

The quaternions are an extension of the complex numbers which were first described by Sir William Rowan Hamilton in 1843. In his description, he gave the equation of the multiplication of the imaginary component similar to that of complex numbers. Many mathematicians have studied the zeros of quaternionic polynomials. Prominent of these, Ivan Niven pioneered a root-finding algorithm in 1941, Gentili and Struppa proved the Fundamental Theorem of Algebra (FTA) for quaternions in 2007. This thesis finds the zeros of quaternionic polynomials using the Fundamental Theorem of Algebra. There are isolated zeros and spheres of zeros. In this thesis, we …

Cohen-Macaulay Properties Of Closed Neighborhood Ideals, Jackson Leaman

All Theses

This thesis investigates Cohen-Macaulay properties of squarefree monomial ideals, which is an important line of inquiry in the field of combinatorial commutative algebra. A famous example of this is Villareal’s edge ideal [11]: given a finite simple graph G with vertices x1, . . . , xn, the edge ideal of G is generated by all the monomials of the form xixj where xi and xj are adjacent in G. Villareal’s characterization of Cohen-Macaulay edge ideals associated to trees is an often-cited result in the literature. This was extended to chordal and bipartite graphs by Herzog, Hibi, and Zheng in …

Bounds For The Augmented Zagreb Index, Ren Qingcuo, Li Wen, Suonan Renqian, Yang Chenxu

Theory & Applications of Graphs

The augmented Zagreb index (AZI for short) of a graph G, introduced by Furtula et al. in 2010, is defined as AZI(G)= Σ v_iv_j ∈ E(G)} (d(v_i)d(v_j)} {d(v_i)+d(v_j)-2)³, where E(G) is the edge set of G, and d(v_i) denotes the degree of the vertex v_i. In this paper, we give some new bounds on general connected graphs, molecular trees and triangle-free graphs.

New Diagonal Graph Ramsey Numbers Of Unicyclic Graphs, Richard M. Low, Ardak Kapbasov

Theory & Applications of Graphs

Grossman conjectured that R(G, G) = 2 ⋅ |V(G)| - 1, for all simple connected unicyclic graphs G of odd girth and |V(G)| ≥ 4. In this note, we prove his conjecture for various classes of G containing a triangle. In addition, new diagonal graph Ramsey numbers are calculated for some classes of simple connected unicyclic graphs of even girth.

Ts-Reconfiguration Of K-Path Vertex Covers In Caterpillars For K \Geq 4, Duc A. Hoang

Theory & Applications of Graphs

A k-path vertex cover (k-PVC) of a graph G is a vertex subset I such that each path on k vertices in G contains at least one member of I. Imagine that a token is placed on each vertex of a k-PVC. Given two k-PVCs I, J of a graph G, thek-Path Vertex Cover Reconfiguration (k-PVCR)} under Token Sliding (TS) problem asks if there is a sequence of k-PVCs between I and J where each intermediate member is obtained from its predecessor by sliding a token from some …

Ramsey Numbers For Connected 2-Colorings Of Complete Graphs, Mark Budden

Theory & Applications of Graphs

In 1978, David Sumner introduced a variation of Ramsey numbers by restricting to 2-colorings in which the subgraphs spanned by edges in each color are connected. This paper continues the study of connected Ramsey numbers, including the evaluation of several cases of trees versus complete graphs.

Matroid Generalizations Of Some Graph Results, Cameron Crenshaw

LSU Doctoral Dissertations

The edges of a graph have natural cyclic orderings. We investigate the matroids for which a similar cyclic ordering of the circuits is possible. A full characterization of the non-binary matroids with this property is given. Evidence of the difficulty of this problem for binary matroids is presented, along with a partial result for binary orderable matroids.

For a graph G, the ratio of |E(G)| to the minimum degree of G has a natural lower bound. For a matroid M that is representable over a finite field, we generalize this to a lower bound on …

Zonality In Graphs, Andrew Bowling

Dissertations

Graph labeling and coloring are among the most popular areas of graph theory due to both the mathematical beauty of these subjects as well as their fascinating applications. While the topic of labeling vertices and edges of graphs has existed for over a century, it was not until 1966 when Alexander Rosa introduced a labeling, later called a graceful labeling, that brought the area of graph labeling to the forefront in graph theory. The subject of graph colorings, on the other hand, goes back to 1852 when the young British mathematician Francis Guthrie observed that the countries in a map …

Irregular Domination In Graphs, Caryn Mays

Dissertations

Domination in graphs has been a popular area of study due in large degree to its applications to modern society as well as the mathematical beauty of the topic. While this area evidently began with the work of Claude Berge in 1958 and Oystein Ore in 1962, domination did not become an active area of research until 1977 with the appearance of a survey paper by Ernest Cockayne and Stephen Hedetniemi. Since then, a large number of variations of domination have surfaced and provided numerous applications to different areas of science and real-life problems. Among these variations are domination parameters …

Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon

Senior Theses

This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.

Optimal Orientations Of Vertex-Multiplications Of Trees With Diameter 4, Willie Han Wah Wong, Eng Guan Tay

Theory & Applications of Graphs

Koh and Tay proved a fundamental classification of G vertex-multiplications into three classes ζ₀, ζ₁ and ζ₂. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class ζ₂. Of interest, G vertex-multiplications are extensions of complete n-partite graphs and Gutin characterised complete bipartite graphs with orientation number 3 (or 4 resp.) via an ingenious use of Sperner's theorem. In this paper, we investigate vertex-multiplications of trees with diameter 4 in ζ₀ (or ζ₁) and exhibit its intricate connections with …

The Determining Number And Cost Of 2-Distinguishing Of Select Kneser Graphs, James E. Garrison

Rose-Hulman Undergraduate Mathematics Journal

A graph $G$ is said to be \emph{d-distinguishable} if there exists a not-necessarily proper coloring with $d$ colors such that only the trivial automorphism preserves the color classes. For a 2-distinguishing labeling, the \emph{ cost of $2$-distinguishing}, denoted $\rho(G),$ is defined as the minimum size of a color class over all $2$-distinguishing colorings of $G$. Our work also utilizes \emph{determining sets} of $G, $ sets of vertices $S \subseteq G$ such that every automorphism of $G$ is uniquely determined by its action on $S.$ The \emph{determining number} of a graph is the size of a smallest determining set. We investigate …

Iterated Jump Graphs, Fran Herr, Legrand Jones Ii

Rose-Hulman Undergraduate Mathematics Journal

The jump graph J(G) of a simple graph G has vertices which represent edges in G where two vertices in J(G) are adjacent if and only if the corresponding edges in G do not share an endpoint. In this paper, we examine sequences of graphs generated by iterating the jump graph operation and characterize the behavior of this sequence for all initial graphs. We build on work by Chartrand et al. who showed that a handful of jump graph sequences terminate and two sequences converge. We extend these results by showing that there are no non-trivial repeating sequences of jump …

The Chromatic Index Of Ring Graphs, Lilian Shaffer

Rose-Hulman Undergraduate Mathematics Journal

The goal of graph edge coloring is to color a graph G with as few colors as possible such that each edge receives a color and that adjacent edges, that is, different edges incident to a common vertex, receive different colors. The chromatic index, denoted χ′(G), is the minimum number of colors required for such a coloring to be possible. There are two important lower bounds for χ′(G) on every graph: maximum degree, denoted ∆(G), and density, denoted ω(G). Combining these two lower bounds, we know that every graph’s chromatic index must be at least ∆(G) or …

Outer Independent Double Italian Domination Of Some Graph Products, Rouhollah Jalaei, Doost Ali Mojdeh

Theory & Applications of Graphs

An outer independent double Italian dominating function on a graph G is a function f:V(G) →{0,1,2,3} for which each vertex x ∈ V(G) with {f(x)∈ {0,1} then Σ_{y ∈ N[x]}f(y) ⩾ 3 and vertices assigned 0 under f are independent. The outer independent double Italian domination number γ_oidI(G) is the minimum weight of an outer independent double Italian dominating function of graph G. In this work, we present some contributions to the study of outer independent double Italian domination of three graph products. We characterize the Cartesian product, lexicographic product and direct product of custom …