Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Graph theory (7)
- Combinatorics (6)
- Graph (3)
- Line graph (2)
- Probability (2)
-
- $K_n$ (1)
- $j$-invariant (1)
- Algebraic geometry (1)
- Aperiodic tile sets (1)
- Applied mathematics (1)
- Arbitrary dimensional tilings (1)
- Asymptotic estimates (1)
- Bi-regular graph (1)
- Broadcasts (1)
- Cellular Automata (1)
- Chinese remainder theorem (1)
- Chromatic number (1)
- Computer virus (1)
- Connected graphs (1)
- Cycle graphs (1)
- DNA (1)
- DNA nanotubes (1)
- Deficient rectangles (1)
- Diophantine equations (1)
- Directed (1)
- Directed Graph (1)
- Discrete math (1)
- Divisibility (1)
- Domination (1)
- Earth-moon Problem (1)
Articles 1 - 30 of 40
Full-Text Articles in Discrete Mathematics and Combinatorics
Asymptotic Enumeration Of K-Bounded Functions Using Toeplitz Matrices, Tiago Cavalcante Trindade, Pedro Martineli
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.
Incremental Increases Between Successive Integers When Raised To The Nth Power, Sutton J. Olesen
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 …
The Intricacies Of Pairwise Modular Multiplicative Inverse In Lucas Numbers, Charles Liu
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.
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.
Counting The Classes Of Projectively-Equivalent Pentagons On Finite Projective Planes Of Prime Order, Maxwell Hosler
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 …
Modeling Virus Diffusion On Social Media Networks With The Smirq Model, Justin Browning, Arnav Mazumder, Gowri Nanda
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 …
Wang Tilings In Arbitrary Dimensions, Ian Tassin
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
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
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
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
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
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).
Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver
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
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
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
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
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
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
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 …
Hurwitz Actions On Reflection Factorizations In Complex Reflection Group G₆, Gaurav Gawankar, Dounia Lazreq, Mehr Rai, Seth Sabar
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.
Irreducibility And Galois Groups Of Random Polynomials, Hanson Hao, Eli Navarro, Henri Stern
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
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
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
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
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
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
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
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
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
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 …