Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Mathematical Sciences Technical Reports (MSTR)

Articles 1 - 30 of 33

Full-Text Articles in Discrete Mathematics and Combinatorics

Gliders On The Sca Model, Alexa Renner Jan 2026

Gliders On The Sca Model, Alexa Renner

Mathematical Sciences Technical Reports (MSTR)

The Stranded Cellular Automata (SCA) model consists of a grid of cells which can each contain between zero and two strands apiece and two turning rules that control when strands turn and when they cross. While patterns on this model have been studied previously, such research has not needed an algebraic description of the model. We provide a formal algebraic definition of patterns on the model, define gliders on the model in a way which is semi-compatible with definitions of gliders in other cellular automata models, and classify all 1- and 2-stranded gliders on this model. In addition, we prove …

Go to article

On The Hexgame, Corwin Jones May 2025

On The Hexgame, Corwin Jones

Mathematical Sciences Technical Reports (MSTR)

The SOMA Cube has been studied by mathematicians for a number of decades, but so far methods for solving three-dimensional space-filling puzzles like the SOMA cube remain numerical; we do not have a means to predict the number of solutions to SOMA-like puzzles. We present a two-dimensional puzzle that shares certain features of the SOMA Cube, with the hope that it will be a more convenient object of study for future research into space-filling/space-covering puzzles.

Go to article

Graph And Group Theoretic Properties Of The Soma Cube And Somap, Kyle Asbury, Ben Glancy Aug 2024

Graph And Group Theoretic Properties Of The Soma Cube And Somap, Kyle Asbury, Ben Glancy

Mathematical Sciences Technical Reports (MSTR)

The SOMA Cube is a puzzle toy in which seven irregularly shaped blocks must be fit together to build a cube. There are 240 distinct solutions to the SOMA Cube. One rainy afternoon, Conway and Guy created a graph of all the solutions by manually building each solution. They called their graph the SOMAP. We studied how the geometric structure of the SOMA Cube pieces informs the graph theoretic properties of the SOMAP, such as subgraphs that can or cannot appear and vertex centrality. We have also used permutation group theory to decipher notation used by Knuth in previous work …

Go to article

Counting Hamming-Graceful Labelings Of Paths, Ashka Dalal May 2024

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.

Go to article

Reversibility Of Stranded Cellular Automata, Allyn Loyd Sep 2023

Reversibility Of Stranded Cellular Automata, Allyn Loyd

Mathematical Sciences Technical Reports (MSTR)

Cellular automata, such as the Stranded Cellular Automaton (SCA) model created by Joshua and Lana Holden, can be used to model weaving patterns. Similar models can be constructed to model macrame patterns, where strands are knotted together. If a rule is injective, then it is reversible. If a rule is surjective, then every configuration has at least one predecessor. In this paper, we will discuss the injectivity and surjectivity of several new SCA models in order to find reversible rules. We will also analyze the number of configurations with no predecessors and the number of configurations that map to the …

Go to article

Structure Of Number Theoretic Graphs, Lee Trent May 2022

Structure Of Number Theoretic Graphs, Lee Trent

Mathematical Sciences Technical Reports (MSTR)

The tools of graph theory can be used to investigate the structure
imposed on the integers by various relations. Here we investigate two
kinds of graphs. The first, a square product graph, takes for its vertices
the integers 1 through n, and draws edges between numbers whose product
is a square. The second, a square product graph, has the same vertex set,
and draws edges between numbers whose sum is a square.
We investigate the structure of these graphs. For square product
graphs, we provide a rather complete characterization of their structure as
a union of disjoint complete graphs. For …

Go to article

The Game Of Life On The Hyperbolic Plane, Yuncong Gu May 2020

The Game Of Life On The Hyperbolic Plane, Yuncong Gu

Mathematical Sciences Technical Reports (MSTR)

In this paper, we work on the Game of Life on the hyperbolic plane. We are interested in different tessellations on the hyperbolic plane and different Game of Life rules. First, we show the exponential growth of polygons on the pentagon tessellation. Moreover, we find that the Group of 3 can keep the boundary of a set not getting smaller. We generalize the existence of still lifes by computer simulations. Also, we will prove some propositions of still lifes and cycles. There exists a still life under rules B1, B2, and S3.

Go to article

Repeat Length Of Patterns On Weaving Products, Zhuochen Liu Nov 2019

Repeat Length Of Patterns On Weaving Products, Zhuochen Liu

Mathematical Sciences Technical Reports (MSTR)

Interlacing strands have been used to create artistic weaving patterns. Repeated patterns form aesthetically pleasing products. This research is a mathematical modeling of weaving products in the real world by using Cellular Automata. The research is conducted by observing the evolution of the model to better understand products in the real world. Specifically, this research focuses on the repeat length of a weaving pattern given the rule of generating it and the configuration of the starting row. Previous studies have shown the range of the repeat length in specific situations. This paper will generalize the precise repeat length in one …

Go to article

Periodicity And Invertibility Of Lattice Gas Cellular Automata, Jiawen Wang May 2019

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 …

Go to article

Stranded Cellular Automaton And Weaving Products, Hao Yang Sep 2018

Stranded Cellular Automaton And Weaving Products, Hao Yang

Mathematical Sciences Technical Reports (MSTR)

In order to analyze weaving products mathematically and find out valid weaving products, it is natural to relate them to Cellular Automaton. They are both generated based on specific rules and some initial conditions. Holden and Holden have created a Stranded Cellular Automaton that can represent common weaving and braiding products. Based on their previous findings, we were able to construct a Java program and analyze various aspects of the automaton they created. This paper will discuss the complexity of the Stranded Cellular Automaton, how to determine whether a weaving product holds together or not based on the automaton and …

Go to article

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh Jul 2014

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Mathematical Sciences Technical Reports (MSTR)

The Welch map x -> gx-1+c is similar to the discrete exponential map x -> gx, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: gx-1+c = x (mod pe) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo pe, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

Go to article

Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts Jul 2011

Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts

Mathematical Sciences Technical Reports (MSTR)

We investigate the structure and cryptographic applications of the Discrete Lambert Map (DLM). The mapping is closely related to the Discrete Log Problem, but has received far less attention since it is considered to be a more complicated map that is likely even harder to invert. However, this mapping is quite important because it underlies the security of the ElGamal Digital Signature Scheme. Using functional graphs induced by this mapping, we were able to find non-random properties that could potentially be used to exploit the ElGamal DSS.

Go to article

The Square Discrete Exponentiation Map, A Wood Jul 2011

The Square Discrete Exponentiation Map, A Wood

Mathematical Sciences Technical Reports (MSTR)

We will examine the square discrete exponentiation map and its properties. The square discrete exponentiation map is a variation on a commonly seen problem in cryptographic algorithms. This paper focuses on understanding the underlying structure of the functional graphs generated by this map. Specifically, this paper focuses on explaining the in-degree of graphs of safe primes, which are primes of the form p = 2q + 1, where q is also prime.

Go to article

Algebraic Solutions To Overdefined Systems With Applications To Cryptanalysis, Eric Crockett May 2011

Algebraic Solutions To Overdefined Systems With Applications To Cryptanalysis, Eric Crockett

Mathematical Sciences Technical Reports (MSTR)

Cryptographic algorithms are based on a wide variety of difficult problems in mathematics. One of these problems is finding a solution to a system of multivariate quadratic equations (MQ). A generalization of this problem is to find a solution to a system of higher order non-linear equations. Both of these problems are NP-hard over any field. Many cryptosystems such as AES, Serpent, Toyocrypt, and others can be reduced to some form of the MQ problem. In this paper we analyze the relinearization and XL algorithms for solving overdetermined systems of non-linear equations, as well as two variations of the XL …

Go to article

Operations Research Methods For Optimization In Radiation Oncology, M Ehrgott, Allen Holder Aug 2009

Operations Research Methods For Optimization In Radiation Oncology, M Ehrgott, Allen Holder

Mathematical Sciences Technical Reports (MSTR)

Operations Research has a successful tradition of applying mathematical analysis to a wide range of applications, with one of the burgeoning areas of growth being in medical physics. The original application was in the optimal design of the influence map for a radiotherapy treatment, a problem that has continued to receive attention. However, operations research has been applied to other clinical problems like patient scheduling, vault design, and image alignment. The overriding theme of this article is to present how techniques in operations research apply to clinical problems, which we accomplish in three parts. First, we present the perspective from …

Go to article

Solving The P-Median Problem With Insights From Discrete Vector Quantization, Gino J. Lim, Allen Holder, Josh Reese Aug 2009

Solving The P-Median Problem With Insights From Discrete Vector Quantization, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

The goals of this paper are twofold. First, we formally equate the p-median problem from facility location to the optimal design of a vector quantizer. Second, we use the equivalence to show that the Maranzana Algorithm can be interpreted as a projected Lloyd Algorithm, a fact that improves complexity. Numerical results verify significant improvements in run-time.

Go to article

A Decomposition Of The Pure Parsimony Problem, Allen Holder, Thomas M. Langley Aug 2009

A Decomposition Of The Pure Parsimony Problem, Allen Holder, Thomas M. Langley

Mathematical Sciences Technical Reports (MSTR)

We partially order a collection of genotypes so that we can represent the problem of inferring the least number of haplotypes in terms of substructures we call g-lattices. This representation allows us to prove that if the genotypes partition into chains with certain structure, then the NP-Hard problem can be solved efficiently. Even without the specified structure, the decomposition shows how to separate the underlying integer programming model into smaller models.

Go to article

A Clustering Approach For Optimizing Beam Angles In Imrt Planning, Gino J. Lim, Allen Holder, Josh Reese Aug 2009

A Clustering Approach For Optimizing Beam Angles In Imrt Planning, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

In this paper we introduce a p-median problem based clustering heuristic for selecting efficient beam angles for intensity-modulated radiation therapy. The essence of the method described here is the clustering of beam angles according to probability that an angle will be observed in the final solution and similarities among different angles and the selection of a representative angle from each of the p resulting cluster cells. We conduct experiments using several combinations of modeling parameters to find the conditions where the heuristic best performs. We found a combination of such parameters that outperformed all other parameters on three of the …

Go to article

Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman Jul 2009

Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman

Mathematical Sciences Technical Reports (MSTR)

The absence of an efficient algorithm to solve the Discrete Logarithm Problem is often exploited in cryptography. While exponentiation with a modulus is extremely fast with a modern computer, the inverse is decidedly not. At the present time, the best algorithms assume that the inverse mapping is completely random. Yet there is at least some structure, and to uncover additional structure that may be useful in constructing or refining algorithms, statistical methods are employed to compare modular exponential mappings to random mappings. More concretely, structure will be defined by representing the mappings as functional graphs and using parameters from graph …

Go to article

Discrete Logarithm Over Composite Moduli, Marcus L. Mace Jul 2009

Discrete Logarithm Over Composite Moduli, Marcus L. Mace

Mathematical Sciences Technical Reports (MSTR)

In an age of digital information, security is of utmost importance. Many encryption schemes, such as the Diffie-Hellman Key Agreement and RSA Cryptosystem, use a function which maps x to y by a modular power map with generator g. The inverse of this function - trying to find x from y - is called the discrete logarithm problem. In most cases, n is a prime number. In some cases, however, n may be a composite number. In particular, we will look at when n = p^b for a prime p. We will show different techniques of obtaining graphs of this …

Go to article

Structural Properties Of Power Digraphs Modulo N, Joseph Kramer-Miller Jul 2009

Structural Properties Of Power Digraphs Modulo N, Joseph Kramer-Miller

Mathematical Sciences Technical Reports (MSTR)

We define G(n, k) to be a directed graph whose set of vertices is {0, 1, ..., n−1} and whose set of edges is defined by a modular relation. We say that G(n, k) is symmetric of order m if we can partition G(n, k) into subgraphs, each containing m components, such that all the components in a subgraph are isomorphic. We develop necessary and sufficient conditions for G(n, k) to contain symmetry when n is odd and square-free. Additionally, we use group theory to describe the structural properties of the subgraph of G(n, k) containing only those vertices relatively …

Go to article

The Discrete Logarithm Problem And Ternary Functional Graphs, Max F. Brugger, Christina A. Frederick Aug 2007

The Discrete Logarithm Problem And Ternary Functional Graphs, Max F. Brugger, Christina A. Frederick

Mathematical Sciences Technical Reports (MSTR)

Encryption is essential to the security of transactions and communications, but the algorithms on which they rely might not be as secure as we all assume. In this paper, we investigate the randomness of the discrete exponentiation function used frequently in encryption. We show how we used exponential generating functions to gain theoretical data for mapping statistics in ternary functional graphs. Then, we compare mapping statistics of discrete exponentiation functional graphs, for a range of primes, with mapping statistics of the respective ternary functional graphs.

Go to article

On The Action Of Weight-Preserving Sets, Matthew Badger Nov 2005

On The Action Of Weight-Preserving Sets, Matthew Badger

Mathematical Sciences Technical Reports (MSTR)

We introduce weight-preserving sets of binary words. Any transformation that respects the row and column weights of a 0-1 matrix can be decomposed as a composition of two types of action on the matrix. We conjecture that weight-preserving sets perform only one type of action, permutations of rows and columns; i.e., weight-preserving sets are cwatsets.

Go to article

Big Cwatsets And Hamming Code, Matthew Davis, Thomas M. Langley, Norah Mazel Oct 2005

Big Cwatsets And Hamming Code, Matthew Davis, Thomas M. Langley, Norah Mazel

Mathematical Sciences Technical Reports (MSTR)

In contrast to Lagrange's Theorem in Finite Group Theory, we show that the ratio of the largest proper cwatset of degree d to the size of binary d-space approaches 1 as d approaches infinity. We show how to explicitly construct large cwatsets as cosets of Hamming Codes, and discuss many open questions that arise.

Go to article

Mapping The Discrete Logarithm, Daniel R. Cloutier Jul 2005

Mapping The Discrete Logarithm, Daniel R. Cloutier

Mathematical Sciences Technical Reports (MSTR)

The discrete logarithm is a problem that surfaces frequently in the field of cryptog- raphy as a result of using the transformation ga mod n. This paper focuses on a prime modulus, p, for which it is shown that the basic structure of the functional graph is largely dependent on an interaction between g and p-1. In fact, there are precisely as many different functional graph structures as there are divisors of p-1. This paper extracts two of these structures, permutations and binary functional graphs. Estimates exist for the shape of a random permutation, but …

Go to article

Fixed Point And Two-Cycles Of The Discrete Logarithm, Joshua Holden Oct 2002

Fixed Point And Two-Cycles Of The Discrete Logarithm, Joshua Holden

Mathematical Sciences Technical Reports (MSTR)

We explore some questions related to one of Brizolis: does every prime p have a pair (g, h) such that h is a fixed point for the discrete logarithm with base g? We extend this question to ask about not only fixed points but also two-cycles. Campbell and Pomerance have not only answered the fixed point question for sufficiently large p but have also rigorously estimated the number of such pairs given certain conditions on g and h. We attempt to give heuristics for similar estimates given other conditions on g and h and also in the case …

Go to article

Applications Of Graph Theory To Separability, Stephen Young Jan 2002

Applications Of Graph Theory To Separability, Stephen Young

Mathematical Sciences Technical Reports (MSTR)

Let S be a surface with a triangular tiling T. Let R be a reflection a side of one of the triangles; so that R is an orientation reversing isometry of the surface. Define M = {s in S |S : Rs = s}. We then say that the surface S separates along the reflection R if S-R has two components. This paper considers the applications of graph theoretic methods to determining whether a reflection is separating or not and compares the algorithmic efficiency of these methods to the current known methods.

Go to article

Automorphic Subsets Of The N-Dimensional Cube Are Translations Of Cwatsets, Matthew Lepinski Apr 1999

Automorphic Subsets Of The N-Dimensional Cube Are Translations Of Cwatsets, Matthew Lepinski

Mathematical Sciences Technical Reports (MSTR)

It is known that automorphic subsets are generalizations of cwatsets. In this paper we show that an automorphic subset is the translation of some cwatset, and therefore that each automorphic subset is internally isomorphic to a cwatset.

Go to article

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer Jul 1998

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

Go to article

The Link Between Scrambling Numbers And Derangements, Barry Balof, Eric Farmer, Jamie Kawabata May 1997

The Link Between Scrambling Numbers And Derangements, Barry Balof, Eric Farmer, Jamie Kawabata

Mathematical Sciences Technical Reports (MSTR)

The group equation abcdef = dabecf can be reduced to the equation xcde = dxec. In general, we are interested in how many variables are needed to represent group equations in which the right side is a permutation of the variables on the left side. Scrambling numbers capture this information about a permutation. In this paper we present several facts about scrambling numbers, and expose a striking relationship between permutations that cannot be reduced and derangements.

Go to article

Next Last