Discrete Mathematics and Combinatorics Commons^™

Big Two And N-Card Poker Probabilities, Brian Wu, Chai Wah Wu

Communications on Number Theory and Combinatorial Theory

Between the poker hands of straight, flush, and full house, which hand is more common? In standard 5-card poker, the order from most common to least common is straight, flush, full house. The same order is true for 7-card poker such as Texas hold'em. However, is the same true for n-card poker for larger n? We study the probability of obtaining these various hands for n-card poker for various values of n≥5. In particular, we derive closed expressions for the probabilities of flush, straight and full house and show that the probability of a flush is less than a straight …

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.

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

Theory and 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 …

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 …

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

Department of Computer Science and Engineering: 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 …

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 …

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 and 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.

Recent Studies On The Super Edge-Magic Deficiency Of Graphs, Rikio Ichishima, Susana C. Lopez, Francesc Muntaner, Yukio Takahashi

Theory and Applications of Graphs

A graph $G$ is called edge-magic if there exists a bijective function $f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert +\left\vert E\left(G\right) \right\vert \right\}$ such that $f\left(u\right) + f\left(v\right) + f\left(uv\right)$ is a constant for each $uv\in E\left( G\right) $. Also, $G$ is called super edge-magic if $f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}$. Furthermore, the super edge-magic deficiency $ \mu_{s}\left(G\right)$ of a graph $G$ is defined to be either the smallest nonnegative integer $n$ with the property that $G \cup nK_{1}$ is super edge-magic or $+ \infty$ if there exists no such …

A Survey Of Maximal K-Degenerate Graphs And K-Trees, Allan Bickle

Theory and Applications of Graphs

This article surveys results on maximal $k$-degenerate graphs, $k$-trees,

and related classes including simple $k$-trees, $k$-paths, maximal

outerplanar graphs, and Apollonian networks. These graphs are important

in many problems in graph theory and computer science. Types of results

surveyed include structural characterizations, enumeration, degree

sets and sequences, chromatic polynomials, algorithms, and related

extremal problems.

On The Singular Pebbling Number Of A Graph, Harmony R. Morris

Rose-Hulman Undergraduate Mathematics Journal

In this paper, we define a new parameter of a connected graph as a spin-off of the pebbling number (which is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble). This new parameter is the singular pebbling number, the smallest t such that a player can be given any configuration of at least t pebbles and any target vertex and can successfully move pebbles so that exactly one pebble ends on the target vertex. We also prove that the singular pebbling number of any graph on 3 or more vertices is equal …

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 …