Discrete Mathematics and Combinatorics Commons^™

Moore Graphs, Trevor Saxton

Williams Honors College, Honors Research Projects

A Moore graph is a simple regular graph, with n vertices, degree d, and diameter k, that satisfies the Moore bound: n = 1 + d (d − 1)k − 1 d − 2 . There are graphs for which the bound is met and in which existence and uniqueness are known. For k = 2 it is known that the Moore bound is achieved for d = 2, 3, 7, with the case of d = 57 conjectured to exist. For k = 3 the bound is achieved for only d = 3 [5]. Due to the construction of …

Measuring The Similarity Between Trees Of Different Order, Camilo Morales

HMC Senior Theses

Graphs encode relationships between data. However, due to their versatility, it is often difficult to generalize the notion of similarity between two graphs using a distance function. Since graphs can represent various data sets, specific distance metrics need to be tailored for questions we are interested in answering or the data set we are working with. This project is motivated by ongoing investigations into the evolution of female gender representation in mathematics. By building off previous work that has taken data from the Mathematics Genealogy Project and modeled this evolution of representation via a tree, we would like to develop …

On Linear Invariants Of Hypergraphs, Clara Chaplin

Honors Theses

We introduce linear invariants of hypergraphs as a way to study hypergraphs by their tensor representations. Our primary research goal is to determine what information linear invariants capture about the hypergraphs they arise from. We first investigate the centroid, which is shown to determine the connected components of a hypergraph. Next, we study the derivations of a hypergraph, and use this linear invariant to define a quotient operator $Q_\mathrm{Der}$ on the collection of all hypergraphs. This operator is shown to be a closure operator in that $Q_\mathrm{Der}(Q_\mathrm{Der}(\mathcal{H}))=Q_\mathrm{Der}(\mathcal{H})$ for any hypergraph $\mathcal{H}$. We apply the operator $Q_\mathrm{Der}$ to synthetically generated hypergraphs, …

On The Combinatorial Invariance For Kazhdan-Lusztig Polynomials, Grover C. Harrell Iii

College of Graduate Studies: Theses & Dissertations

This thesis will be a discussion on the Combinatorial Invariance Conjecture for Kazhdan Lusztig polynomials. The conjecture is widely suspected to be true; and there is an abun dance of computational evidence which supports it. Despite this, no complete proof has been discovered for more than forty years. We will explore some known results about the CIC, particularly those by Dyer, Incitti, Brenti, Caselli, and Marietti.

Apex Graphs And Cographs, Jagdeep Singh, Vaidy Sivaraman, Thomas Zaslavsky

Theory & Applications of Graphs

A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced subgraphs, then so does G^{apex}. We provide an elementary proof of this result.

The hereditary class of cographs consists of all graphs G that can be generated from K_1 using complementation and disjoint union. A graph is an apex cograph if it contains a …

(R2096) Pbib-Designs Associated With Products Of Graphs, Medha Itagi Huilgol, Vidya M.D

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we introduce a design, called “geodetic-design" arising from geodetic sets in a graph. A geodetic-design, over a regular graph is an ordered pair D = (V, B), where V = V (G) and B, the set of all geodetic sets, called blocks, containing vertices belonging to geodetic sets, such that every pair of non-adjacent vertices appears in exactly µ blocks. We first find governing results of a geodetic-design, if it exists, and then get such PBIB-designs for different products of graphs. It is common to have geodetic sets of graphs to be independent sets, hence we extend …

Computational Representation, Analysis And Verification Of Requirements In Engineering Design And Systems Engineering, Chandan Kumar Sahu

All Dissertations

Systems are developed to satisfy a set of requirements derived from stakeholders’ needs, defining the problem space for which the system is created as a feasible solution. The system design process begins with eliciting these requirements and concludes with validating whether the created system meets them. Requirements engineering (RE) encompasses elicitation, representation, analysis, documentation, verification, and validation. However, challenges in RE, such as imprecision in natural language (NL), proprietary restrictions, and a lack of standardized quality metrics, hinder the creation of well-formed and comprehensive requirements. These challenges complicate formalization and analysis of requirements.

This dissertation addresses these challenges by proposing …

A Dynamical Systems Approach For Modeling Malware Propagating Through A Network And Potential Solutions Towards Mitigating Spread, James Johnson

Cybersecurity Undergraduate Research Showcase

Many people draw close parallels between malware propagating through a network and an epidemic spreading through a population. Epidemics are often modeled by a Susceptible-Infected-Recovered (SIR) model, in which a similar system of equations can model the spread of a virus through a computer network, and can be simplified when making assumptions about the network itself and its fixed number of nodes and edges. In this instance, malware propagating in a network also should reflect the network it is propagating through, in which the dynamical system will factor in the nodes of the network and their properties. The system itself …

Codes From Incidence Matrices Of Hypergraphs, Sudipta Mallik, Bahattin Yildiz

Mathematics Faculty Research

Binary codes are constructed from incidence matrices of hypergraphs. A combinatorial description is given for the minimum distances of such codes via a combinatorial tool called “eonv”. This combinatorial approach provides a faster alternative method of finding the minimum distance, which is known to be a hard problem. This is demonstrated on several classes of codes from hypergraphs. In particular the “eonv” method is used to prove that the minimum distance of codes from incidence matrices of complete 3-partite 3-uniform hypergraphs with partite set size of n is n2. A lower bound on the minimum distances of codes from …

Coloring Trivalent Graphs: A Defect Tft Approach, Amit Kumar

LSU Doctoral Dissertations

We show that the combinatorial matter of graph coloring is, in fact, quantum in the sense of satisfying the sum over all the possible intermediate state properties of a path integral. In our case, the topological field theory (TFT) with defects gives meaning to it. This TFT has the property that when evaluated on a planar trivalent graph, it provides the number of Tait-Coloring of it. Defects can be considered as a generalization of groups. With the Klein-four group as a 1-defect condition, we reinterpret graph coloring as sections of a certain bundle, distinguishing a coloring (global-sections) from a coloring …

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 …

Nano Topology And Decision Making In Medical Applications, Samir Mukhtar, Mohamed Shokry, Manar Omran

Journal of Engineering Research

Nano Topology is one of the essential topics that receive special attention from some athletes in the field of General Topology, Operations Research, and Computer Science, because it has a vital role in the generalizing most of the various mathematical concepts. Recently, many efforts have been made to study many types of Nano Topology, as the previous studies lacked real applications in Engineering, Medicine, Pharmacy, and Social Sciences. In this paper, we present some different applications of these studies. The paper is divided into two parts: Firstly, we study the theory of The Nano Topology and investigate its relation with …

New Operation Defined Over Dual-Hesitant Fuzzy Set And Its Application In Diagnostics In Medicine, Manar Mohamed Omran, Reham Abdel-Aziz Abo-Khadra

Journal of Engineering Research

In recent decades, several types of sets, such as fuzzy sets, interval-valued fuzzy sets, intuitionistic fuzzy sets, interval-valued intuitionistic fuzzy sets, type 2 fuzzy sets, type n fuzzy sets, and hesitant fuzzy sets, have been introduced and investigated widely. In this paper, we propose dual hesitant fuzzy sets (DHFSs), which encompass fuzzy sets, intuitionistic fuzzy sets, hesitant fuzzy sets, and fuzzy multi-sets as special cases. Then we investigate the basic operations and properties of DHFSs. We also discuss the relationships among the sets mentioned above, and then propose an extension principle of DHFSs. Additionally, we give an example to illustrate …

Decision-Making In Diagnosing Heart Failure Problems Using Dual Hesitant Fuzzy Sets, Manar Mohamed Omran, Reham Abdel-Aziz Abo-Khadra

Journal of Engineering Research

In recent decades, several types of sets, such as fuzzy sets, interval-valued fuzzy sets, intuitionistic fuzzy sets, interval-valued intuitionistic fuzzy sets, type 2 fuzzy sets, type n fuzzy sets, and hesitant fuzzy sets, have been introduced and investigated widely. In this paper, we propose dual hesitant fuzzy sets (DHFSs), which encompass fuzzy sets, intuitionistic fuzzy sets, hesitant fuzzy sets, and fuzzy multi-sets as special cases. Then we investigate the basic operations and properties of DHFSs. We also discuss the relationships among the sets mentioned above, and then propose an extension principle of DHFSs. Additionally, we give an example to illustrate …

Categorical Chain Conditions For Étale Groupoid Algebras, Sunil Philip

Dissertations, Theses, and Capstone Projects

Let R be a unital commutative ring and G an ample groupoid. Using the topology of the groupoid G, Steinberg defined an étale groupoid algebra RG. These étale groupoid algebras generalize various algebras, including group algebras, commutative algebras over a field generated by idempotents, traditional groupoid algebras, Leavitt path algebras, higher-rank graph algebras, and inverse semigroup algebras. Steinberg later characterized the classical chain conditions for étale groupoid algebras. In this work, we characterize categorically noetherian and artinian, locally noetherian and artinian, and semisimple étale groupoid algebras, thereby generalizing existing results for Leavitt path algebras and introducing new results for inverse …

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 …

Cohen-Macaulay Type Of Open Neighborhood Ideals Of Unmixed Trees, Jounglag Lim

All Theses

Given a tree T and a field k, we define the open neighborhood ideal N(T) of T in k[V] to be the ideal generated by the open neighborhoods of all vertices in the graph. If T is unmixed with respect to the total domination problem, then it is known that N(T) is Cohen-Macaulay. Our goal is to compute the (Cohen-Macaulay) type of k[V]/N(T) using graph theoretical properties of T. We achieve this by using homological algebra and properties of monomial ideals. Along the way, we also provide a different characterization of unmixed trees and a generalization of the total dominating …

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 …

Big Two And N-Card Poker Probabilities, Brian Wu, Chai Wah Wu

Communications on Number Theory and Combinatorial Theory

Between the poker hands of straight, flush, and full house, which hand is more common? In standard 5-card poker, the order from most common to least common is straight, flush, full house. The same order is true for 7-card poker such as Texas hold'em. However, is the same true for n-card poker for larger n? We study the probability of obtaining these various hands for n-card poker for various values of n≥5. In particular, we derive closed expressions for the probabilities of flush, straight and full house and show that the probability of a flush is less than a straight …

Penney’S Game For Permutations, Yixin Lin

Dartmouth College Ph.D Dissertations

We explore the permutation analog of Penney's game for coin flips. Two players, in order, each choose a permutation of length $k\ge3$. Then a sequence of independent random values from a continuous distribution is generated until the relative order of the last $k$ numbers matches one of the chosen permutations, declaring the player who selected that permutation as the winner.

We calculate the winning probabilities for all pairs of permutations of length $3$ and some pairs of length $4$, demonstrating the non-transitive property of this game, consistent with the original word version. Alternatively, we provide formulas for computing the winning …