Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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 …

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.

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.

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(n^k).

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.

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 …

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 …

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 …

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 …

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

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) =a₀+a₁x+a₂x²+···and B(x) =b₀+b₁x+b₂x²+··· is the power series A(x)∗B(x) =a₀b₀+a₁b₁x+a₂b₂x²+···. 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 …

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 G₆, 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.

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.

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 …

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 …

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.

Exponents Of Jacobians Of Graphs And Regular Matroids, Hahn Lheem, Deyuan Li, Carl Joshua Quines, Jessica Zhang

Rose-Hulman Undergraduate Mathematics Journal

Let G be a finite undirected multigraph with no self-loops. The Jacobian Jac (G) is a finite abelian group associated with G whose cardinality is equal to the number of spanning trees of G. There are only a finite number of biconnected graphs G such that the exponent of Jac (G) equals 2 or 3. The definition of a Jacobian can also be extended to regular matroids as a generalization of graphs. We prove that there are finitely many connected regular matroids M such that Jac (M) has exponent 2 and characterize all such matroids.

A Card Trick Based On Error-Correcting Codes, Luis A. Perez

Rose-Hulman Undergraduate Mathematics Journal

Error-correcting codes (ECC), found in coding theory, use methods to handle possible errors that may arise from electronic noise, to a scratch of a CD in a way where they are detected and corrected. Recently, ECC have gone beyond their traditional use. ECC can be used in applications from performing magic tricks to detecting and repairing mutations in DNA sequencing. This paper investigates an application of the Hamming Code, a type of ECC, in the form of a magic trick which uses Andy Liu's description of the Hamming Code through set theory and a known card trick. Finally, connections between …

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.

Dna Self-Assembly Design For Gear Graphs, Chiara Mattamira

Rose-Hulman Undergraduate Mathematics Journal

Application of graph theory to the well-known complementary properties of DNA strands has resulted in new insights about more efficient ways to form DNA nanostructures, which have been discovered as useful tools for drug delivery, biomolecular computing, and biosensors. The key concept underlying DNA nanotechnology is the formation of complete DNA complexes out of a given collection of branched junction molecules. These molecules can be modeled in the abstract as portions of graphs made up of vertices and half-edges, where complete edges are representations of double-stranded DNA pieces that have joined together. For efficiency, one aim is to minimize the …

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 …

Investigating First Returns: The Effect Of Multicolored Vectors, Shakuan Frankson, Myka Terry

Rose-Hulman Undergraduate Mathematics Journal

By definition, a first return is the immediate moment that a path, using vectors in the Cartesian plane, touches the x-axis after leaving it previously from a given point; the initial point is often the origin. In this case, using certain diagonal and horizontal vectors while restricting the movements to the first quadrant will cause almost every first return to end at the point (2n,0), where 2n counts the equal number of up and down steps in a path. The exception will be explained further in the sections below. Using the first returns of Catalan, Schröder, and Motzkin numbers, which …

On The Enumeration Of Shapes, May Cai, Nicholas Liao

Rose-Hulman Undergraduate Mathematics Journal

We define a shape as a union of finitely many line segments. Given an arrangement of lines on a plane, we count the number of shapes in the arrangement by examining the symmetries of the arrangement and applying Burnside's lemma. We further establish a generating function for the number of distinct line segments on a line with k distinguished points. We list all affine line arrangements of four and five line segments, together with the corresponding number of shapes on them.

Iterated Line Graphs On Bi-Regular Graphs And Trees, Brenden Balch

Rose-Hulman Undergraduate Mathematics Journal

In 1965, van Rooij and Wilf considered sequences of line graphs, in which they grouped sequences of line graphs into four categories. We’ll add to their research by presenting results on sequences of line graphs for star graphs and bi-regular graphs. We will then investigate slight variations of star graphs.

Consecutive Prime And Highly Total Prime Labeling In Graphs, Robert Scholle

Rose-Hulman Undergraduate Mathematics Journal

This paper examines the graph-theoretical concepts of consecutive prime labeling and highly total prime labeling. These are variations on prime labeling, introduced by Tout, Dabboucy, and Howalla in 1982. Consecutive prime labeling is defined here for the first time. Consecutive prime labeling requires that the labels of vertices in a graph be relatively prime to the labels of all adjacent vertices as well as all incident edges. We show that all paths, cycles, stars, and complete graphs have a consecutive prime labeling and conjecture that all simple connected graphs have a consecutive prime labeling.

This paper also expands on work …

Combinatorial Identities On Multinomial Coefficients And Graph Theory, Seungho Lee

Rose-Hulman Undergraduate Mathematics Journal

We study combinatorial identities on multinomial coefficients. In particular, we present several new ways to count the connected labeled graphs using multinomial coefficients.

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