Discrete Mathematics and Combinatorics Commons^™

The Vulnerabilities To The Rsa Algorithm And Future Alternative Algorithms To Improve Security, James Johnson

Cybersecurity Undergraduate Research Showcase

The RSA encryption algorithm has secured many large systems, including bank systems, data encryption in emails, several online transactions, etc. Benefiting from the use of asymmetric cryptography and properties of number theory, RSA was widely regarded as one of most difficult algorithms to decrypt without a key, especially since by brute force, breaking the algorithm would take thousands of years. However, in recent times, research has shown that RSA is getting closer to being efficiently decrypted classically, using algebraic methods, (fully cracked through limited bits) in which elliptic-curve cryptography has been thought of as the alternative that is stronger than …

Discrete Complementary Exponential And Sine Integral Functions, Samer Assaf, Tom Cuchta

Mathematics Faculty Research

Discrete analogues of the sine integral and complementary exponential integral functions are investigated. Hypergeometric representation, power series, and Laplace transforms are derived for each. The difficulties in extending these definitions to other common trigonometric integral functions are discussed.

Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham

All Theses

Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.

A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu

Electronic Theses and Dissertations

Graph Neural Networks and Transformers are very powerful frameworks for learning machine learning tasks. While they were evolved separately in diverse fields, current research has revealed some similarities and links between them. This work focuses on bridging the gap between GNNs and Transformers by offering a uniform framework that highlights their similarities and distinctions. We perform positional encodings and identify key properties that make the positional encodings node embeddings. We found that the properties of expressiveness, efficiency and interpretability were achieved in the process. We saw that it is possible to use positional encodings as node embeddings, which can be …

Foundations Of Memory Capacity In Models Of Neural Cognition, Chandradeep Chowdhury

Master's Theses

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the …

Zero-Knowledge Reductions And Confidential Arithmetic, Marvin Jones

All Dissertations

The changes in computing paradigms to shift computations to third parties have resulted in the necessity of these computations to be provable. Zero-knowledge arguments are probabilistic arguments that are used to to verify computations without secret data being leaked to the verifying party.

In this dissertation, we study zero-knowledge arguments with specific focus on reductions. Our main contributions are:

1. Provide a thorough survey in a variety of zero-knowledge techniques and protocols.
2. Prove various results of reductions that can be used to study interactive protocols in terms of subroutines. Additionally, we identify an issue in the analogous definition of zero-knowledge for …

Jumping Frogs On Cyclic Graphs, Jake Mitchell

Honors College Theses

From the traditional game of Solitaire to modern video games like Candy Crush and Five Nights at Freddy’s, single-player games have captivated audiences for gener- ations. We investigate a lesser-known single-player game, the Jumping Frogs problem, on various classes of simple graphs, a graph with no multiple edges or looped ver- tices. We determine whether frogs can be stacked together on one vertex of a given graph. In a graph with k vertices and one frog on each vertex, the frogs must make legal jumps to form a stack of k frogs. The problem is known to be solvable on …

Combinatorially Orthogonal Paths, Sean A. Bailey, David E. Brown, Leroy Beaseley

Communications on Number Theory and Combinatorial Theory

Vectors x=(x₁,x₂,...,x_n)^T and y=(y₁,y₂,...,y_n)^T are combinatorially orthogonal if |{i:x_iy_i≠0}|≠1. An undirected graph G=(V,E) is a combinatorially orthogonal graph if there exists f:V→ℝⁿ such that for any u,v∈V, uv∉E iff f(u) and f(v) are combinatorially orthogonal. We will show that every graph has a combinatorially orthogonal representation. We will show …

Msis-Kadelka: On The Uniqueness Of Network Identification, Alan Veliz-Cuba, Elena Dimitrova

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Msis-Kadelka: Algebraic Methods For Inferring Discrete Models Of Biological Networks, Brandilyn Stigler

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

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.

The Traveling Salesman Problem At Taylor University, Jonathan Jinoo Pawley

Mathematics Student Projects

What is the shortest route to walk to every residence hall on campus, beginning and ending with the same hall? This question can be considered by applying the Traveling Salesman Problem, an easy to understand yet hard to solve problem in the realm of discrete combinatorial optimization. The Traveling Salesman Problem is useful as an introduction to optimization problems, and it also has immensely practical applications. This paper will serve as an introduction to the computational difficulty of the Traveling Salesman Problem and will also explore various approximation algorithms. We will subsequently apply our new understanding of the theory to …

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.

On Nowhere Zero 4-Flows In Regular Matroids, Xiaofeng Wang, Taoye Zhang, Ju Zhou

Theory & Applications of Graphs

Walton and Welsh proved that if a co-loopless regular matroid M does not have a minor in {M(K(3,3)),M^∗(K5)}, then M admits a nowhere zero 4-flow. Lai, Li and Poon proved that if M does not have a minor in {M(K5),M^∗(K5)}, then M admits a nowhere zero 4-flow. We prove that if a co-loopless regular matroid M does not have a minor in {M((P10)_¯3 ),M^∗(K5)}, then M admits a nowhere zero 4-flow where (P10)_¯3 is the graph obtained from the Petersen graph P₁₀by contracting 3 edges of a perfect matching. As …

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 …

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 …

On The Order-Type Complexity Of Words, And Greedy Sidon Sets For Linear Forms, Yin Choi Cheng

Dissertations, Theses, and Capstone Projects

This work consists of two parts. In the first part, we study the order-type complexity of right-infinite words over a finite alphabet, which is defined to be the order types of the set of shifts of said words in lexicographical order. The set of shifts of any aperiodic morphic words whose first letter in the purely-morphic pre-image occurs at least twice in the pre-image has the same order type as Q ∩ (0, 1), Q ∩ (0, 1], or Q ∩ [0, 1). This includes all aperiodic purely-morphic binary words. The order types of uniform-morphic ternary words were also studied, …

Evaluation Of Symmetric Functions And Boolean Functions Over Stochastic Input, Naifeng Liu

Dissertations, Theses, and Capstone Projects

In our daily life, we often face situations where we need to make precise judgments based on initially unknown information, while gathering all the evidence to make informed conclusions can be very costly. In this dissertation, we explore the problem of optimizing the decision-making process under uncertainty, and we focus on problems that can be found in both theoretical computer science and discrete mathematics. The primary goal is to develop approximation algorithms with guaranteed worst-case performance. These algorithms aim to minimize the expected cost of acquiring information necessary for evaluating fundamental functions, such as Boolean and symmetric functions. Furthermore, we …

Fuglede's Conjecture In Some Finite Abelian Groups, Thomas Fallon

Dissertations, Theses, and Capstone Projects

This dissertation thoroughly examines Fuglede's Conjecture within some discrete settings, shedding light on its intricate details. Fuglede's Conjecture establishes a profound connection between the geometric property of being a tiling set and the analytical attribute of being a spectral set. By exploring the conjecture on various discrete settings, this thesis delves into the implications and ramifications of the conjecture, unraveling its implications within the field.

An Analysis Of The Sequence Xn+2 = I M Xn+1 + Xn, David Duncan, Prashant Sansgiry, Ogul Arslan, Jensen Meade

Journal of the South Carolina Academy of Science

We analyze the sequence Xn+2 = imXn+1 + Xn, with X1 = X2 = 1 + i, where i is the imaginary number and m is a real number. Plotting the sequence in the complex plane for different values of m, we see interesting figures from the conic sections. For values of m in the interval (−2, 2) we show that the figures generated are ellipses. We also provide analysis which prove that for certain values of m, the sequence generated is periodic with even period.

The Gamma-Signless Laplacian Adjacency Matrix Of Mixed Graphs, Omar Alomari, Mohammad Abudayah, Manal Ghanem

Theory & Applications of Graphs

The α-Hermitian adjacency matrix H_α of a mixed graph X has been recently introduced. It is a generalization of the adjacency matrix of unoriented graphs. In this paper, we consider a special case of the complex number α. This enables us to define an incidence matrix of mixed graphs. Consequently, we define a generalization of line graphs as well as a generalization of the signless Laplacian adjacency matrix of graphs. We then study the spectral properties of the gamma-signless Laplacian adjacency matrix of a mixed graph. Lastly, we characterize when the signless Laplacian adjacency matrix of …

Signings Of Graphs And Sign-Symmetric Signed Graphs, Ahmad Asiri

Theses and Dissertations

In this dissertation, we investigate various aspects of signed graphs, with a particular focus on signings and sign-symmetric signed graphs. We begin by examining the complete graph on six vertices with one edge deleted ($K_6$\textbackslash e) and explore the different ways of signing this graph up to switching isomorphism. We determine the frustration index (number) of these signings and investigate the existence of sign-symmetric signed graphs. We then extend our study to the $K_6$\textbackslash 2e graph and the McGee graph with exactly two negative edges. We investigate the distinct ways of signing these graphs up to switching isomorphism and demonstrate …

A Machine Learning Approach To Constructing Ramsey Graphs Leads To The Trahtenbrot-Zykov Problem., Emily Hawboldt

Electronic Theses and Dissertations

Attempts at approaching the well-known and difficult problem of constructing Ramsey graphs via machine learning lead to another difficult problem posed by Zykov in 1963 (now commonly referred to as the Trahtenbrot-Zykov problem): For which graphs F does there exist some graph G such that the neighborhood of every vertex in G induces a subgraph isomorphic to F? Chapter 1 provides a brief introduction to graph theory. Chapter 2 introduces Ramsey theory for graphs. Chapter 3 details a reinforcement learning implementation for Ramsey graph construction. The implementation is based on board game software, specifically the AlphaZero program and its …

Dna Self-Assembly Of Trapezohedral Graphs, Hytham Abdelkarim

Electronic Theses, Projects, and Dissertations

Self-assembly is the process of a collection of components combining to form an organized structure without external direction. DNA self-assembly uses multi-armed DNA molecules as the component building blocks. It is desirable to minimize the material used and to minimize genetic waste in the assembly process. We will be using graph theory as a tool to find optimal solutions to problems in DNA self-assembly. The goal of this research is to develop a method or algorithm that will produce optimal tile sets which will self-assemble into a target DNA complex. We will minimize the number of tile and bond-edge types …

One Formula For Non-Prime Numbers: Motivations And Characteristics, Mahmoud Mansour, Kamal Hassan Prof.

Basic Science Engineering

Primes are essential for computer encryption and cryptography, as they are fundamental units of whole numbers and are of the highest importance due to their mathematical qualities. However, identifying a pattern of primes is not easy. Thinking in a different way may get benefits, by considering the opposite side of the problem which means focusing on non-prime numbers. Recently, researchers introduced, the pattern of non-primes in two maximal sets while in this paper, non-primes are presented in one formula. Getting one-way formula for non-primes may pave the way for further applications based on the idea of primes.

Incidence And Laplacian Matrices Of Wheel Graphs And Their Inverses, Jerad Ipsen, Sudipta Mallik

Mathematics Faculty Research

It has been an open problem to find the Moore-Penrose inverses of the incidence, Laplacian, and signless Laplacian matrices of families of graphs except trees and unicyclic graphs. Since the inverse formulas for an odd unicyclic graph and an even unicyclic graph are quite different, we consider wheel graphs as they are formed from odd or even cycles. In this article we solve the open problem for wheel graphs. This work has an interesting connection to inverses of circulant matrices.

Waste Treatment Facility Location For Hotel Chains, Dolores R. Santos-Peñate, Rafael R. Suárez-Vega, Carmen Florido De La Nuez

ITSA 2022 Gran Canaria - 9th Biennial Conference: Corporate Entrepreneurship and Global Tourism Strategies After Covid 19

Tourism generates huge amounts of waste. About half of the waste generated by hotels is food and garden bio-waste. This bio-waste can be used to make compost and pellets. In turn, pellets can be used as an absorbent material in composters and as an energy source. We consider the problem of locating composting and pellet-making facilities so that the bio-waste generated by a chain of hotels can be managed at or close to the generation points. An optimization model is applied to locate the facilities and allocate the waste and products, and several scenarios are analysed. The study shows that, …

A Bit-Parallel Tabu Search Algorithm For Finding Es2 -Optimal And Minimax-Optimal Supersaturated Designs, Luis B. Morales, Dursun A. Bulutoglu

Faculty Publications

We prove the equivalence of two-symbol supersaturated designs (SSDs) with N (even) rows, m columns, s_max=4t+i, where i ∈ {0,2}, t ∈ Z^≥0 and resolvable incomplete block designs (RIBDs) whose any two blocks intersect in at most (N+4t+i)/4 points. Using this equivalence, we formulate the search for two-symbol E(s²)-optimal and minimax-optimal SSDs with s_max ∈ {2,4,6} as a search for RIBDs whose blocks intersect accordingly. This allows developing a bit-parallel tabu search (TS) algorithm. The TS algorithm found E(s²)-optimal and minimax-optimal SSDs achieving the sharpest known E(s²) lower bound with …