Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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.

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