Discrete Mathematics and Combinatorics Commons^™

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 …

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.

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 …

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 …

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 …

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 …

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 …

A Pebbling Game On Powers Of Paths, Garth Isaak, Matthew Prudente, Joseph M. Marcinik Iii

Communications on Number Theory and Combinatorial Theory

Two Player Graph Pebbling is an extension of graph pebbling. Players Mover and Defender use pebbling moves, the act of removing two pebbles from one vertex and placing one pebble on an adjacent vertex, to win. If a specified vertex has a pebble on it, then Mover wins. If a specified vertex is pebble-free and there are no more valid pebbling moves, then Defender wins. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement of m pebbles and for any specified vertex, Mover can win. We specify the …

Discrete Polylogarithm Functions, Tom Cuchta, Dallas Freeman

Mathematics Faculty Research

We investigate a discrete analogue of the polylogarithm function. Difference and summation relations are obtained, as well as its connection to the discrete hypergeometric series.

Representations From Group Actions On Words And Matrices, Joel T. Anderson

Master's Theses

We provide a combinatorial interpretation of the frequency of any irreducible representation of Sn in representations of Sn arising from group actions on words. Recognizing that representations arising from group actions naturally split across orbits yields combinatorial interpretations of the irreducible decompositions of representations from similar group actions. The generalization from group actions on words to group actions on matrices gives rise to representations that prove to be much less transparent. We share the progress made thus far on the open problem of determining the irreducible decomposition of certain representations of Sm × Sn arising from group actions on matrices.

A Survey On Online Matching And Ad Allocation, Ryan Lee

Theses

One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …

Decomposition Of Beatty And Complementary Sequences, Geremías Polanco

Mathematics Sciences: Faculty Publications

In this paper we express the difference of two complementary Beatty sequences, as the sum of two Beatty sequences closely related to them. In the process we introduce a new Algorithm that generalizes the well known Minimum Excluded algorithm and provides a method to generate combinatorially any pair of complementary Beatty sequences.

Δ-Small Intersection Graphs Of Modules, Ahmed H. Alwan

Al-Bahir

Let R be a commutative ring with unit and M be a unitary left R-module. The δ-small intersection graph of non-trivial submodules of , denoted by , is an undirected simple graph whose vertices are the non-trivial submodules of , and two vertices are adjacent if and only if their intersection is a -small submodule of . In this article, we study the interplay between the algebraic properties of , and the graph properties of such as connectivity, completeness and planarity. Moreover, we determine the exact values of the diameter and girth of , as well as give a formula …

Partitions Of R^N With Maximal Seclusion And Their Applications To Reproducible Computation, Jason Vander Woude

Department of Mathematics: Dissertations, Theses, and Student Research

We introduce and investigate a natural problem regarding unit cube tilings/partitions of Euclidean space and also consider broad generalizations of this problem. The problem fits well within a historical context of similar problems and also has applications to the study of reproducibility in randomized computation.

Given $k\in\mathbb{N}$ and $\epsilon\in(0,\infty)$, we define a $(k,\epsilon)$-secluded unit cube partition of $\mathbb{R}^{d}$ to be a unit cube partition of $\mathbb{R}^{d}$ such that for every point $\vec{p}\in\R^d$, the closed $\ell_{\infty}$ $\epsilon$-ball around $\vec{p}$ intersects at most $k$ cubes. The problem is to construct such partitions for each dimension $d$ with the primary goal of minimizing …