Discrete Mathematics and Combinatorics Commons^™

Approval Gap Of Weighted K-Majority Tournaments, Jeremy Coste, Breeann Flesch, Joshua D. Laison, Erin Mcnicholas, Dane Miyata

Theory & Applications of Graphs

A $k$-majority tournament $T$ on a finite set of vertices $V$ is defined by a set of $2k-1$ linear orders on $V$, with an edge $u \to v$ in $T$ if $u>v$ in a majority of the linear orders. We think of the linear orders as voter preferences and the vertices of $T$ as candidates, with an edge $u \to v$ in $T$ if a majority of voters prefer candidate $u$ to candidate $v$. In this paper we introduce weighted $k$-majority tournaments, with each edge $u \to v$ weighted by the number of voters preferring $u$.

We define the …

Counting Hamming-Graceful Labelings Of Paths, Ashka Dalal

Mathematical Sciences Technical Reports (MSTR)

Let Γ be a graph of m edges and n vertices. A Hamming-graceful labeling of Γ labels vertices with binary strings of length m and the edge labels are induced by the Hamming distance between vertex labels. It is known that all paths have Hamming-graceful labelings, thus the question arises, how many possible labelings exist for a path of a given size. We develop an algebraic way to generate labelings, conjecture a method for counting, prove this for small examples, and verify larger examples using a Python program.

Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi

School of Computing: Dissertations, Theses, and Student Research

The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the …

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 Forget Time For Random Walks On Trees Of A Fixed Diameter, Lola R. Vescovo

Mathematics, Statistics, and Computer Science Honors Projects

A mixing measure is the expected length of a random walk on a graph given a set of starting and stopping conditions. We study a mixing measure called the forget time. Given a graph G, the pessimal access time for a target distribution is the expected length of an optimal stopping rule to that target distribution, starting from the worst initial vertex. The forget time of G is the smallest pessimal access time among all possible target distributions. We prove that the balanced double broom maximizes the forget time on the set of trees on n vertices with diameter …

Finding Combinatorial Patterns In Real Valued Omics Data, Kenneth Smith

Dissertations

Precision medicine is a healthcare approach which tailors disease prevention and treatment to an individual, based on their genetics, environment, lifestyle, and physiological state. These factors interact to produce biological changes that can be measured to produce data called omics, and include genomics, lipidomics, and proteomics. Despite the abundance of omics data and analysis techniques, researchers still struggle to identify biological findings that replicate across data sets and translate into clinical applications. In this dissertation, we employ combinatorial optimization techniques to improve upon three steps in the precision medicine analysis pipeline: 1) data cleaning, 2) community detection, and 3) feature …

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 …

2-Accessibility Of The Lucas Numbers/Fibonacci Like Sequences/Wythoff Array, Cameron Lejeune

Mathematics Senior Capstone Papers

In this project we will be delving into the combinatorics side of mathematics, with basic a graph theory idea such as set coloring. It will be a continuation of a question formed by the works of Bruce M. Landman, and Aaron Robertson, ”3-Accessibility of the Fibonacci Numbers.” They were able to prove the Fibonacci Numbers to be 2-Accessible, and while they did not supply the induction proof, we were able to construct and provide a proof. This project will use their lemmas and propositions to attempt to prove 2-Accessibility of the Lucas Numbers, Fibonacci-like sequences, and the Zeckendorf-Wythoff Array.

An Exploration Of The Sums Of Two Squares And Pentagonal Numbers, Jacob Von Tress

Mathematics Senior Capstone Papers

In the field of number theory, square numbers are very significant, and finding the sums of square numbers is a topic of certain interest to mathematicians. The most immediate application for adding together two square numbers is to identify Pythagorean triples. However, apart from seeking sums of two squares that are squares themselves, interesting patterns emerge that have fascinated number theorists for decades. Particularly, the distribution of a number’s divisors can explicitly determine how many ways that number can be written as a sum of two squares. Furthermore, pentagonal numbers, similar to square numbers, can be visualized by drawing a …

Matroids Stemming From The Maximal Relaxation Of Graphic Matroids, Landen Nguyen

Mathematics Senior Capstone Papers

This research explores the base perspective for maximal relaxation of graphic matroids. We begin by covering the required knowledge of graph theory and the basics of matroid theory required to conduct this research such as definitions of matroids up to the definitions of relaxation, hyperplanes, and uniform matroids. We then analyze the conjecture in matroids obtained from simple connected graphs.

Four Colorful Methods For Finding The Chromatic Polynomial, Emerson Statom

Mathematics Senior Capstone Papers

Mathematicians apply algebraic graph theory to address and interpret problems arising out of data structures and optimization. For example, graph coloring problems have intrigued mathematicians and computer scientists alike. The chromatic polynomial was created to help solve such problems. This research aims to create a greater understanding of the underlying structures behind chromatic polynomials by analyzing the algebraic, deletion-contraction, and color partition methods. Each method has differing applications, but by viewing them all together, this research hopes to show the depth of this most interesting subject in a condensed manner.

Congruences Of The Sums Of The First Rp Fibonacci Numbers, Tyler Warzynak

Mathematics Senior Capstone Papers

This paper serves as an extension/application of a method detailed by Chang et. al. in two separate papers which worked with sums modulo p for combinatorial sequences, positive integers r, and prime numbers p. Using a known formula, the Fibonacci numbers were converted into a sum of binomial coefficients to apply the aforementioned method. A hypothesis was formed using computational methods, where a pattern was observed to hold for the first 50,000 prime numbers. This claim was then proven following the methodology from Chang et. al. using properties of Laurent polynomials, definitions and theorems related to the Fibonacci numbers, and …

Discrete Macaulay-Steiner Geometry, Nikola Kuzmanovski

Dissertations and Doctoral Documents, University of Nebraska-Lincoln, 2023–

This thesis is concerned with discrete isoperimetric inequalities and Hilbert functions. Two generalizations of the Ahlswede-Cai local global principle are presented. These results give positive answers to two questions posed by Harper. One of these results is achieved by proving uniqueness of the lexicographic and colexicographic orders in two dimensions. The other result generalizes the technique which is commonly known as compression and includes almost all previously published results in this direction. The Ahlswede-Cai local global principle is a direct corollary of this result. Optimal downsets are studied in rectangles and triangles. All optimal downsets are found. The main result …

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 …

Wang Tilings In Arbitrary Dimensions, Ian Tassin

Rose-Hulman Undergraduate Mathematics Journal

This paper makes a new observation about arbitrary dimensional Wang Tilings,
demonstrating that any d -dimensional tile set that can tile periodically along d − 1 axes must be able to tile periodically along all axes.
This work also summarizes work on Wang Tiles up to the present day, including
definitions for various aspects of Wang Tilings such as periodicity and the validity of a tiling. Additionally, we extend the familiar 2D definitions for Wang Tiles and associated properties into arbitrary dimensional spaces. While there has been previous discussion of arbitrary dimensional Wang Tiles in other works, it has been …

Strongly I-Bicritical Graphs, Michelle Edwards, Gary Macgillivray, Shahla Nasserasr

Theory & Applications of Graphs

A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown …

The Distinguishing Number Of Some Special Kind Of Graphs, Arti Salat, Amit Sharma

Applications and Applied Mathematics: An International Journal (AAM)

In the present study, the distinguishing number of some different graphs is examined where different graphs like the coconut tree graph, firecracker graph, jellyfish graph, triangular book graph, and banana tree graph have been taken into account. The major goal of the proposed study is to understand the distinguishing number of different graphs for better insights. It is evident from the results that the distinguishing numbers and automorphism groups of the above-mentioned graphs have been carried out successfully.

Some Generalizations Of Corona Product Of Two Graphs, Aparajita Borah, Gajendra Pratap Singh

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we are seeking to conceptualize the notion of corona product of two graphs to contrive some special types of graphs. That is, here our attempt is to regenerate a familiar graph as a product graph. We are considering seven familiar graphs here to reconstruct them with the help of corona product of two graphs. Such types of families of the graphs and operations can be used to study biological pathways as well as to find the optimal order and size for the special types of graphs.

Optimizing Buying Strategies In Dominion, Nikolas A. Koutroulakis

Rose-Hulman Undergraduate Mathematics Journal

Dominion is a deck-building card game that simulates competing lords growing their kingdoms. Here we wish to optimize a strategy called Big Money by modeling the game as a Markov chain and utilizing the associated transition matrices to simulate the game. We provide additional analysis of a variation on this strategy known as Big Money Terminal Draw. Our results show that player's should prioritize buying provinces over improving their deck. Furthermore, we derive heuristics to guide a player's decision making for a Big Money Terminal Draw Deck. In particular, we show that buying a second Smithy is always more optimal …

Seating Groups And 'What A Coincidence!': Mathematics In The Making And How It Gets Presented, Peter J. Rowlett

Journal of Humanistic Mathematics

Mathematics is often presented as a neatly polished finished product, yet its development is messy and often full of mis-steps that could have been avoided with hindsight. An experience with a puzzle illustrates this conflict. The puzzle asks for the probability that a group of four and a group of two are seated adjacently within a hundred seats, and is solved using combinatorics techniques.