Discrete Mathematics and Combinatorics Commons^™

Decisive Neutrality, Restricted Decisive Neutrality, And Split Decisive Neutrality On Median Semilattices And Median Graphs., Ulf Högnäs

Electronic Theses and Dissertations

Consensus functions on finite median semilattices and finite median graphs are studied from an axiomatic point of view. We start with a new axiomatic characterization of majority rule on a large class of median semilattices we call sufficient. A key axiom in this result is the restricted decisive neutrality condition. This condition is a restricted version of the more well-known axiom of decisive neutrality given in [4]. Our theorem is an extension of the main result given in [7]. Another main result is a complete characterization of the class of consensus on a finite median semilattice that satisfies the axioms …

Optimizing Networking Topologies With Shortest Path Algorithms, Jordan Sahs

UNO Student Research and Creative Activity Fair

Communication networks tend to contain redundant devices and mediums of transmission, thus the need to locate, document, and optimize networks is increasingly becoming necessary. However, many people do not know where to start the optimization progress. What is network topology? What is this “Shortest Path Problem”, and how can it be used to better my network? These questions are presented, taught, and answered within this paper. To supplement the reader’s understanding there are thirty-eight figures in the paper that are used to help convey and compartmentalize the learning process needed to grasp the materials presented in the ending sections.

In …

Mathematical Magic: A Study Of Number Puzzles, Nicasio M. Velez

Rose-Hulman Undergraduate Mathematics Journal

Within this paper, we will briefly review the history of a collection of number puzzles which take the shape of squares, polygons, and polyhedra in both modular and nonmodular arithmetic. Among other results, we develop construction techniques for solutions of both Modulo and regular Magic Squares. For other polygons in nonmodular arithmetic, specifically of order 3, we present a proof of why there are only four Magic Triangles using linear algebra, disprove the existence of the Magic Tetrahedron in two ways, and utilizing the infamous 3-SUM combinatorics problem we disprove the existence of the Magic Octahedron.

Exploring Winning Strategies For The Game Of Cycles, Kailee Lin

HMC Senior Theses

This report details my adventures exploring the Game of Cycles in search of winning strategies. I started by studying combinatorial game theory with hopes to use the Sprague-Grundy Theorem and the structure of Nimbers to gain insight for the Game of Cycles. In the second semester, I pivoted to studying specific types of boards instead. In this thesis I show that variations of the mirror-reverse strategy developed by Alvarado et al. in the original Game of Cycles paper can be used to win on additional game boards with special structure, such as lollipops, steering wheel locks, and 3-spoke trees. Additionally …

The Name Tag Problem, Christian Carley

Rose-Hulman Undergraduate Mathematics Journal

The Name Tag Problem is a thought experiment that, when formalized, serves as an introduction to the concept of an orthomorphism of $\Zn$. Orthomorphisms are a type of group permutation and their graphs are used to construct mutually orthogonal Latin squares, affine planes and other objects. This paper walks through the formalization of the Name Tag Problem and its linear solutions, which center around modular arithmetic. The characterization of which linear mappings give rise to these solutions developed in this paper can be used to calculate the exact number of linear orthomorphisms for any additive group Z/nZ, which is demonstrated …

H-Discrete Fractional Model Of Tumor Growth And Anticancer Effects Of Mono And Combination Therapies, Kamala Dadashova

Masters Theses & Specialist Projects

In this thesis, we focus on h–discrete and h–discrete fractional representation of a pharmacokinetics-pharmacodynamics (PK-PD) model which describes tumor growth considering time on hNa, where h>0. First, we introduce some definitions, lemmas and theorems on both h–discrete and h–discrete fractional calculus in the preliminary section. In Chapter 3, we work on the PD model with delay by exam ining nabla h–discrete equations and nabla h–discrete fractional equations as well as variation of constants formulas, accordingly. We introduce our model and solve it using theorems we proved in the last section of the indicated chapter. When we do simulation for …

Phylogenetic Networks And Functions That Relate Them, Drew Scalzo

Williams Honors College, Honors Research Projects

Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate …

Interval Valued Neutrosophic Shortest Path Problem By A* Algorithm, Florentin Smarandache, S. Khrisna Prabha, Said Broumi

Branch Mathematics and Statistics Faculty and Staff Publications

Many researchers have been proposing various algorithms to unravel different types of fuzzy shortest path problems. There are many algorithms like Dijkstra’s, Bellman-Ford,Floyd-Warshall and kruskal’s etc are existing for solving the shortest path problems. In this work a shortest path problem with interval valued neutrosophic numbers is investigated using the proposed algorithm. A* algorithm is extensively applied in pathfinding and graph traversal.Unlike the other algorithms mentioned above, A* algorithm entails heuristic function to uncover the cost of path that traverses through the particular state. In the structured work A* algorithm is applied to unravel the length of the shortest path …

Maximality And Applications Of Subword-Closed Languages, Rhys Davis Jones

UNF Graduate Theses and Dissertations

Characterizing languages D that are maximal with the property that D^* ⊆ S^⊗ is an important problem in formal language theory with applications to coding theory and DNA codewords. Given a finite set of words of a fixed length S, the constraint, we consider its subword closure, S^⊗, the set of words whose subwords of that fixed length are all in the constraint. We investigate these maximal languages and present characterizations for them. These characterizations use strongly connected components of deterministic finite automata and lead to polynomial time algorithms for generating such languages. We prove that …

A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler

Senior Independent Study Theses

Santorini is a two player combinatorial board game. Santorini bears resemblance to the graph theory game of Geography, a game of moving and deleting vertices on a graph. We explore Santorini with game theory, complexity theory, and artificial intelligence. We present David Lichtenstein’s proof that Geography is PSPACE-hard and adapt the proof for generalized forms of Santorini. Last, we discuss the development of an AI built for a software implementation of Santorini and present a number of improvements to that AI.

Controllability And Observability Of Linear Nabla Discrete Fractional Systems, Tilekbek Zhoroev

Masters Theses & Specialist Projects

The main purpose of this thesis to examine the controllability and observability of the linear discrete fractional systems. First we introduce the problem and continue with the review of some basic definitions and concepts of fractional calculus which are widely used to develop the theory of this subject. In Chapter 3, we give the unique solution of the fractional difference equation involving the Riemann-Liouville operator of real order between zero and one. Additionally we study the sequential fractional difference equations and describe the way to obtain the state-space repre- sentation of the sequential fractional difference equations. In Chapter 4, we …

Roman Domination Cover Rubbling, Nicholas Carney

Electronic Theses and Dissertations

In this thesis, we introduce Roman domination cover rubbling as an extension of domination cover rubbling. We define a parameter on a graph $G$ called the \textit{Roman domination cover rubbling number}, denoted $\rho_{R}(G)$, as the smallest number of pebbles, so that from any initial configuration of those pebbles on $G$, it is possible to obtain a configuration which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the …

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 …

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 …

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.

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

Special Subset Vertex Multisubgraphs For Multi Networks, Florentin Smarandache, W.B. Vasantha Kandasamy, Ilanthenral K

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors study special type of subset vertex multi subgraphs; these multi subgraphs can be directed or otherwise. Another special feature of these subset vertex multigraphs is that we are aware of the elements in each vertex set and how it affects the structure of both subset vertex multisubgraphs and edge multisubgraphs. It is pertinent to record at this juncture that certain ego centric directed multistar graphs become empty on the removal of one edge, there by theorising the importance, and giving certain postulates how to safely form ego centric multi networks. Given any subset vertex multigraph we …

Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier

College of Graduate Studies: Theses & Dissertations

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound …

On Coding For Partial Erasure Channels, Carolyn Mayer

Department of Mathematics: Dissertations, Theses, and Student Research

Error correcting codes have been essential to the technology we use in everyday life in digital storage, wireless communication, barcodes, and much more. Different channel models are used for different types of communication (for example, if information is sent to one person or to many people) and different types of errors. Partial erasure channels were recently introduced to model applications in which some information remains after an erasure event. These remnants of information may be used to increase the chances of successful decoding. We introduce a new partial erasure channel in which partial erasures correspond to individual bit erasures in …

Strong Degrees In Single Valued Neutrosophic Graphs, Florentin Smarandache, Said Broumi, Assia Bakali, Seema Mehra, Mohamed Talea, Manjeet Singh

Branch Mathematics and Statistics Faculty and Staff Publications

The concept of single valued neutrosophic graphs (SVNGs) generalizes the concept of fuzzy graphs and intuitionistic fuzzy graphs. The purpose of this research paper is to define different types of strong degrees in SVNGs and introduce novel concepts, such as the vertex truth-membership, vertex indeterminacy-membership and falsity-membership sequence in SVNG with proof and numerical illustrations.

Design And Analysis Of Graph-Based Codes Using Algebraic Lifts And Decoding Networks, Allison Beemer

Department of Mathematics: Dissertations, Theses, and Student Research

Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The …

Summary Of The Special Issue “Neutrosophic Information Theory And Applications” At “Information” Journal, Florentin Smarandache, Jun Ye

Branch Mathematics and Statistics Faculty and Staff Publications

Over a period of seven months (August 2017–February 2018), the Special Issue dedicated to “Neutrosophic Information Theory and Applications” by the “Information” journal (ISSN 2078-2489), located in Basel, Switzerland, was a success. The Guest Editors, Prof. Dr. Florentin Smarandache from the University of New Mexico (USA) and Prof. Dr. Jun Ye from the Shaoxing University (China), were happy to select—helped by a team of neutrosophic reviewers from around the world, and by the “Information” journal editors themselves—and publish twelve important neutrosophic papers, authored by 27 authors and coauthors. There were a variety of neutrosophic topics studied and used by the …

Self-Assembly Of Dna Graphs And Postman Tours, Katie Bakewell

UNF Graduate Theses and Dissertations

DNA graph structures can self-assemble from branched junction molecules to yield solutions to computational problems. Self-assembly of graphs have previously been shown to give polynomial time solutions to hard computational problems such as 3-SAT and k-colorability problems. Jonoska et al. have proposed studying self-assembly of graphs topologically, considering the boundary components of their thickened graphs, which allows for reading the solutions to computational problems through reporter strands. We discuss weighting algorithms and consider applications of self-assembly of graphs and the boundary components of their thickened graphs to problems involving minimal weight Eulerian walks such as the Chinese Postman Problem and …

Subset Vertex Graphs For Social Networks, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of subset vertex graph using the vertex set as the subset of the power set P(S), S is assumed in this book to be finite; however it can be finite or infinite. We have defined two types of subset vertex graphs, one is directed and the other one is not directed. The most important fact which must be kept in record is that for a given set of vertices there exists one and only one subset vertex graph be it of type I or type II. Several important and …

Distributive Lattice Models Of The Type C One-Rowed Weyl Group Symmetric Functions, William Atkins

Murray State Theses and Dissertations

We present two families of diamond-colored distributive lattices – one known and one new – that we can show are models of the type C one-rowed Weyl symmetric functions. These lattices are constructed using certain sequences of positive integers that are visualized as filling the boxes of one-rowed partition diagrams. We show how natural orderings of these one-rowed tableaux produce our distributive lattices as sublattices of a more general object, and how a natural coloring of the edges of the associated order diagrams yields a certain diamond-coloring property. We show that each edge-colored lattice possesses a certain structure that is …

Ns-K-Nn: Neutrosophic Set-Based K-Nearest Neighbors Classifier, Florentin Smarandache, Yaman Akbulut, Abdulkadir Sengur, Yanhui Guo

Branch Mathematics and Statistics Faculty and Staff Publications

k-nearest neighbors (k-NN), which is known to be a simple and efficient approach, is a non-parametric supervised classifier. It aims to determine the class label of an unknown sample by its k-nearest neighbors that are stored in a training set. The k-nearest neighbors are determined based on some distance functions. Although k-NN produces successful results, there have been some extensions for improving its precision. The neutrosophic set (NS) defines three memberships namely T, I and F. T, I, and F shows the truth membership degree, the false membership degree, and the indeterminacy membership degree, respectively. In this paper, the NS …

Vertex Weighted Spectral Clustering, Mohammad Masum

Electronic Theses and Dissertations

Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to …

Efficiently Representing The Integer Factorization Problem Using Binary Decision Diagrams, David Skidmore

All Graduate Plan B and other Reports, Spring 1920 to Spring 2023

Let p be a prime positive integer and let α be a positive integer greater than 1. A method is given to reduce the problem of finding a nontrivial factorization of α to the problem of finding a solution to a system of modulo p polynomial congruences where each variable in the system is constrained to the set {0,...,p − 1}. In the case that p = 2 it is shown that each polynomial in the system can be represented by an ordered binary decision diagram with size less than 20.25log₂(α)³ + 16.5log₂(α)² + …

Complex Neutrosophic Graphs Of Type 1, Florentin Smarandache, Said Broumi, Assia Bakali, Mohamed Talea

Branch Mathematics and Statistics Faculty and Staff Publications

In this paper, we introduced a new neutrosophic graphs called complex neutrosophic graphs of type1 (CNG1) and presented a matrix representation for it and studied some properties of this new concept. The concept of CNG1 is an extension of generalized fuzzy graphs of type 1 (GFG1) and generalized single valued neutrosophic graphs of type 1 (GSVNG1).