Discrete Mathematics and Combinatorics Commons^™

Choose Your Own Adventure: An Analysis Of Interactive Gamebooks Using Graph Theory, D'Andre Adams, Daniela Beckelhymer, Alison Marr

Journal of Humanistic Mathematics

"BEWARE and WARNING! This book is different from other books. You and YOU ALONE are in charge of what happens in this story." This is the captivating introduction to every book in the interactive novel series, Choose Your Own Adventure (CYOA). Our project uses the mathematical field of graph theory to analyze forty books from the CYOA book series for ages 9-12. We first began by drawing the digraphs of each book. Then we analyzed these digraphs by collecting structural data such as longest path length (i.e. longest story length) and number of vertices with outdegree zero (i.e. number …

Merge Trees In Discrete Morse Theory, Benjamin Johnson

Mathematics Summer Fellows

The field of topological data analysis seeks to use techniques in topology to study large data sets. The hope is that rather than single quantities that summarize the data, such as mean or standard deviation, information about the data can be learned by studying the overall ``shape” of the data. One way to summarize this data is through a merge tree. Merge trees can be thought of as keeping track of certain clusters of data and determining when they merge together. In this paper, we will study merge trees induced by a discrete Morse function on a tree. Under a …

Some Theoretical Links Between Shortest Path Filters And Minimum Spanning Tree Filters, Sravan Danda, Aditya Challa, B. S.Daya Sagar, Laurent Najman

Journal Articles

Edge-aware filtering is an important pre-processing step in many computer vision applications. In the literature, there exist several versions of collaborative edge-aware filters based on spanning trees and shortest path heuristics which work well in practice. For instance, tree filter (TF) which is recently proposed based on a minimum spanning tree (MST) heuristic yields promising results in many filtering applications. However, links between the tree-based filters and shortest path-based filters are faintly explored. In this article, we introduce an edge-aware generalization of the TF termed as UMST filter based on a subgraph generated by edges of all MSTs. The major …

Properties Of Functionally Alexandroff Topologies And Their Lattice, Jacob Scott Menix

Masters Theses & Specialist Projects

This thesis explores functionally Alexandroff topologies and the order theory asso- ciated when considering the collection of such topologies on some set X. We present several theorems about the properties of these topologies as well as their partially ordered set.

The first chapter introduces functionally Alexandroff topologies and motivates why this work is of interest to topologists. This chapter explains the historical context of this relatively new type of topology and how this work relates to previous work in topology. Chapter 2 presents several theorems describing properties of functionally Alexandroff topologies ad presents a characterization for the functionally Alexandroff topologies …

A Zero-Suppressed Binary Decision Diagram Approach For Constrained Path Enumeration, Renzo Roel P. Tan, Jun Kawahara, Agnes Garciano, Immanuel Sin

Mathematics Faculty Publications

Combinatorial optimization over graphs has been the subject of research. Recently, the solution of such problems by enumeration using a compact data structure called the zero-suppressed binary decision diagram was proposed and studied. The paper augments the existing frontier-based search method of construction and puts forth a technique for accommodating additional constraints during computation. The shortest and longest path problems for the Osaka Metro transit network are simultaneously solved as demonstration. Furthermore, a comparison of the approach with a conventional integer programming method is presented towards justifying the effectiveness of the algorithm.

The Mystery Of Frobenius Symmetry, Maciej Piwowarczyk

DePaul Discoveries

In this project we studied the mathematical concept of the Frobenius number and some curious patterns that come with it. One common example of the Frobenius number is the Coin Problem: If handed two denominations of coins, say 4¢ and 5¢, and asked to create all possible values, we will eventually find ourselves in a position where we can make any value. With 4¢ and 5¢ coins, we can create any value above 11¢, but not 11¢ itself. So, that makes 11 the Frobenius number of 4 and 5. What we explore in this paper is a pattern we call …

Graph Pebbling Algorithms And Lemke Graphs, Charles A. Cusack, Aaron Green, Airat Bekmetjev, Mark Powers

Faculty Publications

Given a simple, connected graph, a pebbling configuration (or just configuration) is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r. A configuration is solvable if every vertex is reachable. The pebbling number π(G) of a graph G is the minimum integer such that every configuration of size π(G) on G …

On The Bures–Wasserstein Distance Between Positive Definite Matrices, Rajendra Bhatia, T. Jain, Yongdo Lim

Journal Articles

The metric d(A,B)=trA+trB−2tr(A1∕2BA1∕2)1∕21∕2 on the manifold of n×n positive definite matrices arises in various optimisation problems, in quantum information and in the theory of optimal transport. It is also related to Riemannian geometry. In the first part of this paper we study this metric from the perspective of matrix analysis, simplifying and unifying various proofs. Then we develop a theory of a mean of two, and a barycentre of several, positive definite matrices with respect to this metric. We explain some recent work on a fixed point iteration for computing this Wasserstein barycentre. Our emphasis is on ideas natural to …

New Approach Of Deterministic Key Pre-Distribution Scheme Using Triangle Free Quasi Symmetric Designs, Debashis Ghosh, Joydeb Pal

Applications and Applied Mathematics: An International Journal (AAM)

A wireless sensor network (WSN) consists of tiny autonomous sensor nodes with some constraints. There are organizations having moderately necessitates of these kind of networks. So, security become an indispensable concern in WSN, due to potential adversaries. To overcome the security problem, keys are pre-loaded to the nodes before deployment. Among all key distribution schemes, deterministic key pre-distribution scheme (KPS) using combinatorial design is efficient regarding security aspect. In this paper, a deterministic approach, based on combinatorial design, for key assignment before the network deployment has been presented. Here the quasi-symmetric design which is of triangle-free is being used to …

Pascal's Triangle, Pascal's Pyramid, And The Trinomial Triangle, Antonio Saucedo Jr.

Electronic Theses, Projects, and Dissertations

Many properties have been found hidden in Pascal's triangle. In this paper, we will present several known properties in Pascal's triangle as well as the properties that lift to different extensions of the triangle, namely Pascal's pyramid and the trinomial triangle. We will tailor our interest towards Fermat numbers and the hockey stick property. We will also show the importance of the hockey stick properties by using them to prove a property in the trinomial triangle.

Analogues Between Leibniz's Harmonic Triangle And Pascal's Arithmetic Triangle, Lacey Taylor James

Electronic Theses, Projects, and Dissertations

This paper will discuss the analogues between Leibniz's Harmonic Triangle and Pascal's Arithmetic Triangle by utilizing mathematical proving techniques like partial sums, committees, telescoping, mathematical induction and applying George Polya's perspective. The topics presented in this paper will show that Pascal's triangle and Leibniz's triangle both have hockey stick type patterns, patterns of sums within shapes, and have the natural numbers, triangular numbers, tetrahedral numbers, and pentatope numbers hidden within. In addition, this paper will show how Pascal's Arithmetic Triangle can be used to construct Leibniz's Harmonic Triangle and show how both triangles relate to combinatorics and arithmetic through the …

Nonstandard Dice That Both Count For Card Craps, Mark Bollman

International Conference on Gambling & Risk Taking

The Pala Casino in California deals Card Craps using a red die numbered {2; 2; 2; 5; 5; 5} and a blue die numbered {3; 3; 3; 4; 4; 4}. Two cards from a special 36-card deck, which contains one card bearing each of the 36 ways in which two dice can land when rolled, are dealt: one each face down to a red space and a blue space. When the dice are rolled, the higher number determines which of the cards is flipped over.

A moment's reflection reveals that Pala's blue die is unnecessary. The card selection process can …

On The Intersection Number Of Finite Groups, Humberto Bautista Serrano

Math Theses

Let G be a finite, nontrivial group. In a paper in 1994, Cohn defined the covering number of a finite group as the minimum number of nontrivial proper subgroups whose union is equal to the whole group. This concept has received considerable attention lately, mainly due to the importance of recent discoveries. In this thesis we study a dual concept to the covering number. We define the intersection number of a finite group as the minimum number of maximal subgroups whose intersection is equal to the Frattini subgroup. Similarly we define the inconjugate intersection number of a finite group as …

Behind The Tiles: Mathematics Of Carcassonne, Emilia Dewyngaert

Across the Bridge: The Merrimack Undergraduate Research Journal

Carcassonne is a tile-placing game where players take turns choosing a tile from a stack and attempting to create a city, road or a meadow. In addition to this, there is a river expansion pack that has river tiles to be placed. This paper focuses on how many different layouts or configurations of the river expansion pack can be created. It also discusses the Matlab code adapted to create a simulation of possible configurations of the river expansion pack.

Maximum Oriented Forcing Number For Complete Graphs, Yair Caro, Ryan Pepper

Theory & Applications of Graphs

The maximum oriented k-forcing number of a simple graph G, written MOF_k(G), is the maximum directed k-forcing number among all orientations of G. This invariant was recently introduced by Caro, Davila and Pepper in [6], and in the current paper we study the special case where G is the complete graph with order n, denoted K_n . While MOF_k(G) is an invariant for the underlying simple graph G, MOF_k(K_n) can also be interpreted as an interesting property for tournaments. Our main results …

On Monochromatic Pairs With Nondecreasing Diameters, Adam O'Neal, Michael W. Schroeder

Mathematics Faculty Research

Let n m r t be positive integers and Δ : [n] → [r]. We say Δ is (m, r, t) - permissible if there exist t disjoint m-sets B₁,…,B_t contained in [n] for which

1. |Δ(B_i)| = 1 for each i = 1,2,…, t.
2. max(B_i) < min(B_i+1) for each i = 1,2,…, t − 1, and
3. max(B_i) − min(B_i) ≤ max(B_i+1) − max(B_i+1) for each i = …

Matching Preclusion Of The Generalized Petersen Graph, Ajay Arora, Eddie Cheng, Christopher Melekian

Theory & Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph with no perfect matchings. In this paper we determine the matching preclusion number for the generalized Petersen graph P(n,k) and classify the optimal sets.

Periodicity And Invertibility Of Lattice Gas Cellular Automata, Jiawen Wang

Mathematical Sciences Technical Reports (MSTR)

A cellular automaton is a type of mathematical system that models the behavior of a set of cells with discrete values in progressing time steps. The often complicated behaviors of cellular automata are studied in computer science, mathematics, biology, and other science related fields. Lattice gas cellular automata are used to simulate the movements of particles. This thesis aims to discuss the properties of lattice gas models, including periodicity and invertibility, and to examine their accuracy in reflecting the physics of particles in real life. Analysis of elementary cellular automata is presented to introduce the concept of cellular automata and …

Generalizations Of The Arcsine Distribution, Rebecca Rasnick

Electronic Theses and Dissertations

The arcsine distribution looks at the fraction of time one player is winning in a fair coin toss game and has been studied for over a hundred years. There has been little further work on how the distribution changes when the coin tosses are not fair or when a player has already won the initial coin tosses or, equivalently, starts with a lead. This thesis will first cover a proof of the arcsine distribution. Then, we explore how the distribution changes when the coin the is unfair. Finally, we will explore the distribution when one person has won the first …

Taking Notes: Generating Twelve-Tone Music With Mathematics, Nathan Molder

Electronic Theses and Dissertations

There has often been a connection between music and mathematics. The world of musical composition is full of combinations of orderings of different musical notes, each of which has different sound quality, length, and em phasis. One of the more intricate composition styles is twelve-tone music, where twelve unique notes (up to octave isomorphism) must be used before they can be repeated. In this thesis, we aim to show multiple ways in which mathematics can be used directly to compose twelve-tone musical scores.

Perfect Double Roman Domination Of Trees, Ayotunde Egunjobi

Electronic Theses and Dissertations

See supplemental content for abstract

Mathematical Models: The Lanchester Equations And The Zombie Apocalypse, Hailey Bauer

Undergraduate Theses and Capstone Projects

This research study used mathematical models to analyze and depicted specific battle situations and the outcomes of the zombie apocalypse. The original models that predicted warfare were the Lanchester models, while the zombie apocalypse models were fictional expansions upon mathematical models used to examine infectious diseases. In this paper, I analyzed and compared different mathematical models by examining each model’s set of assumptions and the impact of the change in variables on the population classes. The purpose of this study was to understand the basics of the discrete dynamical systems and to determine the similarities between imaginary and realistic models. …

Series-Parallel Operations With Alpha-Graphs, Christian Barrientos, Sarah Minion

Theory & Applications of Graphs

Among difference vertex labelings of graphs, α-labelings are the most restrictive one. A graph is an α-graph if it admits an α-labeling. In this work, we study a new alternative to construct α-graphs using, the well-known, series-parallel operations on smaller α-graphs. As an application of the series operation, we show that all members of a subfamily of all trees with maximum degree 4, obtained using vertex amalgamation of copies of the path Ρ₁₁}, are α-graphs. We also show that the one-point union of up to four copies of Κ_n,n is an …

Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang

Theory & Applications of Graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu [18] recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of G, denoted by fmp(G), is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of G, denoted by fsmp(G), is the minimum number of vertices and edges whose deletion …

Blackjack: The Math Behind The Cards, Hanna Blanchard

Mathematics Senior Capstone Papers

In this paper the reader will learn about the math behind the cards in the game of Blackjack. Blackjack or “21” has been played around the world with various rules and regulations in both professional and informal environments. The ultimate objective of the game is to receive a total card value of 21, or as close to 21 as possible without exceeding it, from the cards in a player’s hand in order to beat the dealer’s total. The goal of this project is to calculate the probabilities of various hands to determine the best strategies to win 21. The probabilities …

Greatest Common Divisor: Algorithm And Proof, Mary K. Flagg

Number Theory

No abstract provided.

Congruence Relations Mod 2 For (2 X 4^T + 1)-Colored Partitions, Nicholas Torello

Senior Theses

Let p_r(n) denote the difference between the number of r-colored partitions of n into an even number of distinct parts and into an odd number of distinct parts. Inspired by proofs involving modular forms of the Hirschhorn-Sellers Conjecture, we prove a similar congruence for p_r(n). Using the Jacobi Triple Product identity, we discover a much stricter congruence for p_3(n).

The Knill Graph Dimension From Clique Cover, Evatt Salinger, Dr. Kassahun Betre

Seaver College Research And Scholarly Achievement Symposium

In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim (G1 + G2) = 1 + dim G1 + dim G2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order KN will have dimension N − 1.

Triangle Packing On Tripartite Graphs Is Hard, Peter A. Bradshaw

Rose-Hulman Undergraduate Mathematics Journal

The problem of finding a maximum matching on a bipartite graph is well-understood and can be solved using the augmenting path algorithm. However, the similar problem of finding a large set of vertex-disjoint triangles on tripartite graphs has not received much attention. In this paper, we define a set of vertex-disjoint triangles as a “tratching.” The problem of finding a tratching that covers all vertices of a tripartite graph can be shown to be NP-complete using a reduction from the three-dimensional matching problem. In this paper, however, we introduce a new construction that allows us to emulate Boolean circuits using …

Graphs, Random Walks, And The Tower Of Hanoi, Stephanie Egler

Rose-Hulman Undergraduate Mathematics Journal

The Tower of Hanoi puzzle with its disks and poles is familiar to students in mathematics and computing. Typically used as a classroom example of the important phenomenon of recursion, the puzzle has also been intensively studied its own right, using graph theory, probability, and other tools. The subject of this paper is “Hanoi graphs”, that is, graphs that portray all the possible arrangements of the puzzle, together with all the possible moves from one arrangement to another. These graphs are not only fascinating in their own right, but they shed considerable light on the nature of the puzzle itself. …