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

Discrete Mathematics and Combinatorics Commons™

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

Rose-Hulman Institute of Technology

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 1 - 30 of 74

Full-Text Articles in Discrete Mathematics and Combinatorics

Asymptotic Enumeration Of K-Bounded Functions Using Toeplitz Matrices, Tiago Cavalcante Trindade, Pedro Martineli Aug 2026

Asymptotic Enumeration Of K-Bounded Functions Using Toeplitz Matrices, Tiago Cavalcante Trindade, Pedro Martineli

Rose-Hulman Undergraduate Mathematics Journal

We introduce the concept of $(\alpha, \lambda)$-bounded functions, characterized by limited local variation, which is especially useful in discrete sets. Initially, we formally define these functions and investigate their fundamental properties, highlighting significant differences from continuous functions. The main result obtained is the asymptotic estimate of $a(n, k)$, representing the number of functions from $[n]$ to $[n]$ that are $k$-bounded with respect to the Manhattan distance. The proof of this result combines Toeplitz matrices with a well-known inequality from graph theory.

Go to article

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

Incremental Increases Between Successive Integers When Raised To The Nth Power, Sutton J. Olesen Sep 2025

Incremental Increases Between Successive Integers When Raised To The Nth Power, Sutton J. Olesen

Rose-Hulman Undergraduate Mathematics Journal

For thousands of years, the beautiful field of number theory has captivated mathematicians with its elegant simplicity. Positive integers continue to reveal properties and relationships that are a joy to uncover, and in this paper, we investigate a pattern involving exponents and factorials while exploring some common notations in the field of number theory. Combinatorics, the field dealing with the mathematics of counting and arranging, also holds a presence in this paper. Pascal’s Triangle–the foundation of binomial expressions, also comes into play due to its tight relationship with combinatorics. Pascal’s Identity, the property that builds the triangle, becomes very useful …

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

The Intricacies Of Pairwise Modular Multiplicative Inverse In Lucas Numbers, Charles Liu Mar 2025

The Intricacies Of Pairwise Modular Multiplicative Inverse In Lucas Numbers, Charles Liu

Rose-Hulman Undergraduate Mathematics Journal

Let (p,q) be a pair of relatively prime integers greater than 1. The pairwise modular multiplicative inverse (PMMI) of (p,q) is defined as the unique pair of positive integers (p′, q′) such that p p′ ≡ 1 (mod q), p′ < q, qq′ ≡ 1 (mod p), q′ < p. In this paper, we determine all pairs of Lucas numbers such that their PMMIs are pairs of Lucas numbers.

Go to article

Counting Rotational Subsets Of The Circle $\Mathbb{R}/ \Mathbb{Z}$ Under The Angle-Multiplying Map $T\Mapsto Dt$, Ian Tan Jan 2025

Counting Rotational Subsets Of The Circle $\Mathbb{R}/ \Mathbb{Z}$ Under The Angle-Multiplying Map $T\Mapsto Dt$, Ian Tan

Rose-Hulman Undergraduate Mathematics Journal

A rotational set is a finite subset $A$ of the unit circle $\mathbb{R}/ \mathbb{Z}$ such that the angle-multiplying map $\sigma_{d}:t\mapsto dt$ maps $A$ onto itself by a cyclic permutation of its elements. Each rotational set has a geometric rotation number $p/q$. Lisa Goldberg introduced these sets to study the dynamics of complex polynomial maps. In this paper, we provide a necessary and sufficient condition for a set to be $\sigma_{d}$-rotational with rotation number $p/q$. As applications of our condition, we recover two classical results and enumerate $\sigma_d$-rotational sets with rotation number $p/q$ that consist of a given number of orbits.

Go to article

Counting The Classes Of Projectively-Equivalent Pentagons On Finite Projective Planes Of Prime Order, Maxwell Hosler Oct 2024

Counting The Classes Of Projectively-Equivalent Pentagons On Finite Projective Planes Of Prime Order, Maxwell Hosler

Rose-Hulman Undergraduate Mathematics Journal

In this paper, we examine the number of equivalence classes of pentagons on finite projective planes of prime order under projective transformations. We are interested in those pentagons in general position, meaning that no three vertices are collinear. We consider those planes which can be constructed from finite fields of prime order, and use algebraic techniques to characterize them by their symmetries. We are able to construct a unique representative for each pentagon class with nontrivial symmetries. We can then leverage this fact to count classes of pentagons in general. We discover that there are (1/10)((p+3)(p-3)+4 …

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

Modeling Virus Diffusion On Social Media Networks With The Smirq Model, Justin Browning, Arnav Mazumder, Gowri Nanda Jul 2024

Modeling Virus Diffusion On Social Media Networks With The Smirq Model, Justin Browning, Arnav Mazumder, Gowri Nanda

Rose-Hulman Undergraduate Mathematics Journal

As social networking services become more complex and widespread, users become increasingly susceptible to becoming infected with malware and risk their data being compromised. In the United States, it costs the government billions of dollars annually to handle malware attacks. Additionally, computer viruses can be spread through schools, businesses, and individuals’ personal devices and accounts. Malware affecting larger groups of people causes problems with privacy, personal files, and financial security. Thus, we developed the probabilistic SMIRQ (pSMIRQ) model that shows how a virus spreads through a generated network as a way to track and prevent future viruses. Our model is …

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

Wang Tilings In Arbitrary Dimensions, Ian Tassin Mar 2024

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 …

Go to article

Optimizing Buying Strategies In Dominion, Nikolas A. Koutroulakis Feb 2024

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 …

Go to article

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

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 …

Go to article

Divisibility Probabilities For Products Of Randomly Chosen Integers, Noah Y. Fine Oct 2023

Divisibility Probabilities For Products Of Randomly Chosen Integers, Noah Y. Fine

Rose-Hulman Undergraduate Mathematics Journal

We find a formula for the probability that the product of n positive integers, chosen at random, is divisible by some integer d. We do this via an inductive application of the Chinese Remainder Theorem, generating functions, and several other combinatorial arguments. Additionally, we apply this formula to find a unique, but slow, probabilistic primality test.

Go to article

Structure Of A Total Independent Set, Lewis Stanton Oct 2023

Structure Of A Total Independent Set, Lewis Stanton

Rose-Hulman Undergraduate Mathematics Journal

Let $G$ be a simple, connected and finite graph with order $n$. Denote the independence number, edge independence number and total independence number by $\alpha(G), \alpha'(G)$ and $\alpha''(G)$ respectively. This paper establishes an upper bound for $\alpha''(G)$ in terms of $\alpha(G)$, $\alpha'(G)$ and $n$. We also describe the possible structures for a total independent set containing a given number of elements.

Go to article

K-Distinct Lattice Paths, Eric J. Yager, Marcus Engstrom Sep 2023

K-Distinct Lattice Paths, Eric J. Yager, Marcus Engstrom

Rose-Hulman Undergraduate Mathematics Journal

Lattice paths can be used to model scheduling and routing problems, and, therefore, identifying maximum sets of k-distinct paths is of general interest. We extend the work previously done by Gillman et. al. to determine the order of a maximum set of k-distinct lattice paths. In particular, we disprove a conjecture by Gillman that a greedy algorithm gives this maximum order and also refine an upper bound given by Brewer et. al. We illustrate that brute force is an inefficient method to determine the maximum order, as it has time complexity O(nk).

Go to article

Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver Sep 2023

Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver

Rose-Hulman Undergraduate Mathematics Journal

This paper utilizes heuristic algorithms for determining graph thickness in order to attempt to find a 10-chromatic thickness-2 graph. Doing so would eliminate 9 colors as a potential solution to the Earth-moon Problem. An empirical analysis of the algorithms made by the author are provided. Additionally, the paper lists various graphs that may or nearly have a thickness of 2, which may be solutions if one can find two planar subgraphs that partition all of the graph’s edges.

Go to article

The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$, Yasmin Aguillon, Xingyu Cheng, Spencer Eddins, Pedro Morales Sep 2023

The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$, Yasmin Aguillon, Xingyu Cheng, Spencer Eddins, Pedro Morales

Rose-Hulman Undergraduate Mathematics Journal

DNA and other polymer chains in confined spaces behave like closed loops. Arsuaga et al. \cite{AB} introduced the uniform random polygon model in order to better understand such loops in confined spaces using probabilistic and knot theoretical techniques, giving some classification on the mean squared linking number of such loops. Flapan and Kozai \cite{flapan2016linking} extended these techniques to find the mean sum of squared linking numbers for random linear embeddings of complete graphs $K_n$ and found it to have order $\Theta(n(n!))$. We further these ideas by inspecting random piecewise-linear embeddings of complete graphs and give introductory-level summaries of the ideas …

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

The Determining Number And Cost Of 2-Distinguishing Of Select Kneser Graphs, James E. Garrison Mar 2023

The Determining Number And Cost Of 2-Distinguishing Of Select Kneser Graphs, James E. Garrison

Rose-Hulman Undergraduate Mathematics Journal

A graph $G$ is said to be \emph{d-distinguishable} if there exists a not-necessarily proper coloring with $d$ colors such that only the trivial automorphism preserves the color classes. For a 2-distinguishing labeling, the \emph{ cost of $2$-distinguishing}, denoted $\rho(G),$ is defined as the minimum size of a color class over all $2$-distinguishing colorings of $G$. Our work also utilizes \emph{determining sets} of $G, $ sets of vertices $S \subseteq G$ such that every automorphism of $G$ is uniquely determined by its action on $S.$ The \emph{determining number} of a graph is the size of a smallest determining set. We investigate …

Go to article

Iterated Jump Graphs, Fran Herr, Legrand Jones Ii Feb 2023

Iterated Jump Graphs, Fran Herr, Legrand Jones Ii

Rose-Hulman Undergraduate Mathematics Journal

The jump graph J(G) of a simple graph G has vertices which represent edges in G where two vertices in J(G) are adjacent if and only if the corresponding edges in G do not share an endpoint. In this paper, we examine sequences of graphs generated by iterating the jump graph operation and characterize the behavior of this sequence for all initial graphs. We build on work by Chartrand et al. who showed that a handful of jump graph sequences terminate and two sequences converge. We extend these results by showing that there are no non-trivial repeating sequences of jump …

Go to article

The Chromatic Index Of Ring Graphs, Lilian Shaffer Feb 2023

The Chromatic Index Of Ring Graphs, Lilian Shaffer

Rose-Hulman Undergraduate Mathematics Journal

The goal of graph edge coloring is to color a graph G with as few colors as possible such that each edge receives a color and that adjacent edges, that is, different edges incident to a common vertex, receive different colors. The chromatic index, denoted χ′(G), is the minimum number of colors required for such a coloring to be possible. There are two important lower bounds for χ′(G) on every graph: maximum degree, denoted ∆(G), and density, denoted ω(G). Combining these two lower bounds, we know that every graph’s chromatic index must be at least ∆(G) or …

Go to article

Tiling Rectangles And 2-Deficient Rectangles With L-Pentominoes, Monica Kane May 2022

Tiling Rectangles And 2-Deficient Rectangles With L-Pentominoes, Monica Kane

Rose-Hulman Undergraduate Mathematics Journal

We investigate tiling rectangles and 2-deficient rectangles with L-pentominoes. First, we determine exactly when a rectangle can be tiled with L-pentominoes. We then determine locations for pairs of unit squares that can always be removed from an m × n rectangle to produce a tileable 2-deficient rectangle when m ≡ 1 (mod 5), n ≡ 2 (mod 5) and when m ≡ 3 (mod 5), n ≡ 4 (mod 5).

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

A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar Apr 2022

A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar

Rose-Hulman Undergraduate Mathematics Journal

The Hadamard product (denoted by∗) of two power series A(x) =a0+a1x+a2x2+···and B(x) =b0+b1x+b2x2+··· is the power series A(x)∗B(x) =a0b0+a1b1x+a2b2x2+···. Although it is well known that the Hadamard product of two rational functions is also rational, a closed form expression of the Hadamard product of rational functions has not been found. Since any rational power series can be expanded by partial fractions as a polynomial plus a sum of power series …

Go to article

Hurwitz Actions On Reflection Factorizations In Complex Reflection Group G₆, Gaurav Gawankar, Dounia Lazreq, Mehr Rai, Seth Sabar Dec 2021

Hurwitz Actions On Reflection Factorizations In Complex Reflection Group G₆, Gaurav Gawankar, Dounia Lazreq, Mehr Rai, Seth Sabar

Rose-Hulman Undergraduate Mathematics Journal

We show that in the complex reflection group G6, reflection factorizations of a Coxeter element that have the same length and multiset of conjugacy classes are in the same Hurwitz orbit. This confirms one case of a conjecture of Lewis and Reiner.

Go to article

Irreducibility And Galois Groups Of Random Polynomials, Hanson Hao, Eli Navarro, Henri Stern Jul 2021

Irreducibility And Galois Groups Of Random Polynomials, Hanson Hao, Eli Navarro, Henri Stern

Rose-Hulman Undergraduate Mathematics Journal

In 2015, I. Rivin introduced an effective method to bound the number of irreducible integral polynomials with fixed degree d and height at most N. In this paper, we give a brief summary of this result and discuss the precision of Rivin's arguments for special classes of polynomials. We also give elementary proofs of classic results on Galois groups of cubic trinomials.

Go to article

Repeat Length Of Patterns On Weaving Products, Zhuochen Liu Jul 2021

Repeat Length Of Patterns On Weaving Products, Zhuochen Liu

Rose-Hulman Undergraduate Mathematics Journal

On weaving products such as fabrics and silk, people use interlacing strands to create artistic 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 …

Go to article

New Results On Subtractive Magic Graphs, Matthew J. Ko, Jason Pinto, Aaron Davis Jul 2021

New Results On Subtractive Magic Graphs, Matthew J. Ko, Jason Pinto, Aaron Davis

Rose-Hulman Undergraduate Mathematics Journal

For any edge xy in a directed graph, the subtractive edge-weight is the sum of the label of xy and the label of y minus the label of x. Similarly, for any vertex z in a directed graph, the subtractive vertex-weight of z is the sum of the label of z and all edges directed into z and all the labels of edges that are directed away from z. A subtractive magic graph has every subtractive edge and vertex weight equal to some constant k. In this paper, we will discuss variations of subtractive magic labelings on …

Go to article

Directed Graphs Of The Finite Tropical Semiring, Caden G. Zonnefeld Jul 2021

Directed Graphs Of The Finite Tropical Semiring, Caden G. Zonnefeld

Rose-Hulman Undergraduate Mathematics Journal

The focus of this paper lies at the intersection of the fields of tropical algebra and graph theory. In particular the interaction between tropical semirings and directed graphs is investigated. Originally studied by Lipvoski, the directed graph of a ring is useful in identifying properties within the algebraic structure of a ring. This work builds off research completed by Beyer and Fields, Hausken and Skinner, and Ang and Shulte in constructing directed graphs from rings. However, we will investigate the relationship (x, y)→(min(x, y), x+y) as defined by the operations of tropical algebra and applied to tropical semirings.

Go to article

Next Last