Discrete Mathematics and Combinatorics Commons^™

The Combinatorics Of Integer Partitions Enumerated By Some Exotic Weights, Hunter Waldron

Dissertations, Master's Theses and Master's Reports

Identities of integer partitions generally state that two dissimilar appearing families of partitions are in fact equinumerous when both are restricted to any fixed size. Euler's theorem is a classic example of such an identity, which equates the number of partitions with odd parts to the number of partitions with distinct parts. Lately, analogs of known partition identities involving weights other than size have begun to attract research interest. This dissertation is an investigation of two such weights. In Chapter 2, we study Schmidt weights, which count only parts with indices belonging to some given subset of the positive integers. …

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 …

On Pattern Avoidance And Dynamical Algebraic Combinatorics, Benjamin Adenbaum

Dartmouth College Ph.D Dissertations

Over the past decade since the term `dynamical algebraic combinatorics' was coined there has been a tremendous amount of activity in the field. Adding to that growing body of work this thesis hopes to be a step towards a broader study of pattern avoidance within dynamical algebraic combinatorics and helps initiate that by considering an action of rowmotion on 321-avoiding permutations. Additionally within we show the first known instance of piecewise-linear rowmotion periodicity for an infinite family of posets that does not follow from a more general birational result. Finally we show that the code of permutation restricted to permutations …

Boolean Group Structure In Class Groups Of Positive Definite Quadratic Forms Of Primitive Discriminant, Christopher Albert Hudert Jr.

Departmental Honors & Graduate Capstone Projects

It is possible to completely describe the representation of any integer by binary quadratic forms of a given discriminant when the discriminant’s class group is a Boolean group (also known as an elementary abelian 2-group). For other discriminants, we can partially describe the representation using the structure of the class group. The goal of the present project is to find whether any class group with 32 elements and a primitive positive definite discriminant is a Boolean group. We find that no such class group is Boolean.

An Alternate Proof For The Top-Heavy Conjecture On Partition Lattices Using Shellability, Brian Macdonald, Josh Hallam

Honors Thesis

A partially ordered set, or poset, is governed by an ordering that may or may not relate any pair of objects in the set. Both the bonds of a graph and the partitions of a set are partially ordered, and their poset structure can be depicted visually in a Hasse diagram. The partitions of {1, 2, ..., n} form a particularly important poset known as the partition lattice Πn. It is isomorphic to the bond lattice of the complete graph Kn, making it a special case of the family of bond lattices. Dowling and Wilson’s 1975 Top-Heavy Conjecture states that …