Discrete Mathematics and Combinatorics Commons^™

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 …

Approval Gap Of Weighted K-Majority Tournaments, Jeremy Coste, Breeann Flesch, Joshua D. Laison, Erin Mcnicholas, Dane Miyata

Theory & Applications of Graphs

A $k$-majority tournament $T$ on a finite set of vertices $V$ is defined by a set of $2k-1$ linear orders on $V$, with an edge $u \to v$ in $T$ if $u>v$ in a majority of the linear orders. We think of the linear orders as voter preferences and the vertices of $T$ as candidates, with an edge $u \to v$ in $T$ if a majority of voters prefer candidate $u$ to candidate $v$. In this paper we introduce weighted $k$-majority tournaments, with each edge $u \to v$ weighted by the number of voters preferring $u$.

We define the …

Counting Hamming-Graceful Labelings Of Paths, Ashka Dalal

Mathematical Sciences Technical Reports (MSTR)

Let Γ be a graph of m edges and n vertices. A Hamming-graceful labeling of Γ labels vertices with binary strings of length m and the edge labels are induced by the Hamming distance between vertex labels. It is known that all paths have Hamming-graceful labelings, thus the question arises, how many possible labelings exist for a path of a given size. We develop an algebraic way to generate labelings, conjecture a method for counting, prove this for small examples, and verify larger examples using a Python program.

The Forget Time For Random Walks On Trees Of A Fixed Diameter, Lola R. Vescovo

Mathematics, Statistics, and Computer Science Honors Projects

A mixing measure is the expected length of a random walk on a graph given a set of starting and stopping conditions. We study a mixing measure called the forget time. Given a graph G, the pessimal access time for a target distribution is the expected length of an optimal stopping rule to that target distribution, starting from the worst initial vertex. The forget time of G is the smallest pessimal access time among all possible target distributions. We prove that the balanced double broom maximizes the forget time on the set of trees on n vertices with diameter …

Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi

School of Computing: Dissertations, Theses, and Student Research

The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the …

Domination In Graphs And The Removal Of A Matching, Geoffrey Boyer

All Theses

We consider how the domination number of an undirected graph changes on the removal of a maximal matching. It is straightforward that there are graphs where no matching removal increases the domination number, and where some matching removal doubles the domination number. We show that in a nontrivial tree there is always a matching removal that increases the domination number; and if a graph has domination number at least $2$ there is always a maximal matching removal that does not double the domination number. We show that these results are sharp and discuss related questions.

Finding Combinatorial Patterns In Real Valued Omics Data, Kenneth Smith

Dissertations

Precision medicine is a healthcare approach which tailors disease prevention and treatment to an individual, based on their genetics, environment, lifestyle, and physiological state. These factors interact to produce biological changes that can be measured to produce data called omics, and include genomics, lipidomics, and proteomics. Despite the abundance of omics data and analysis techniques, researchers still struggle to identify biological findings that replicate across data sets and translate into clinical applications. In this dissertation, we employ combinatorial optimization techniques to improve upon three steps in the precision medicine analysis pipeline: 1) data cleaning, 2) community detection, and 3) feature …

The Modular Generalized Springer Correspondence For The Symplectic Group, Joseph Dorta

LSU Doctoral Dissertations

The Modular Generalized Springer Correspondence (MGSC), as developed by Achar, Juteau, Henderson, and Riche, stands as a significant extension of the early groundwork laid by Lusztig's Springer Correspondence in characteristic zero which provided crucial insights into the representation theory of finite groups of Lie type. Building upon Lusztig's work, a generalized version of the Springer Correspondence was later formulated to encompass broader contexts.

In the realm of modular representation theory, Juteau's efforts gave rise to the Modular Springer Correspondence, offering a framework to explore the interplay between algebraic geometry and representation theory in positive characteristic. Achar, Juteau, Henderson, and Riche …

2-Accessibility Of The Lucas Numbers/Fibonacci Like Sequences/Wythoff Array, Cameron Lejeune

Mathematics Senior Capstone Papers

In this project we will be delving into the combinatorics side of mathematics, with basic a graph theory idea such as set coloring. It will be a continuation of a question formed by the works of Bruce M. Landman, and Aaron Robertson, ”3-Accessibility of the Fibonacci Numbers.” They were able to prove the Fibonacci Numbers to be 2-Accessible, and while they did not supply the induction proof, we were able to construct and provide a proof. This project will use their lemmas and propositions to attempt to prove 2-Accessibility of the Lucas Numbers, Fibonacci-like sequences, and the Zeckendorf-Wythoff Array.

An Exploration Of The Sums Of Two Squares And Pentagonal Numbers, Jacob Von Tress

Mathematics Senior Capstone Papers

In the field of number theory, square numbers are very significant, and finding the sums of square numbers is a topic of certain interest to mathematicians. The most immediate application for adding together two square numbers is to identify Pythagorean triples. However, apart from seeking sums of two squares that are squares themselves, interesting patterns emerge that have fascinated number theorists for decades. Particularly, the distribution of a number’s divisors can explicitly determine how many ways that number can be written as a sum of two squares. Furthermore, pentagonal numbers, similar to square numbers, can be visualized by drawing a …

Matroids Stemming From The Maximal Relaxation Of Graphic Matroids, Landen Nguyen

Mathematics Senior Capstone Papers

This research explores the base perspective for maximal relaxation of graphic matroids. We begin by covering the required knowledge of graph theory and the basics of matroid theory required to conduct this research such as definitions of matroids up to the definitions of relaxation, hyperplanes, and uniform matroids. We then analyze the conjecture in matroids obtained from simple connected graphs.

Four Colorful Methods For Finding The Chromatic Polynomial, Emerson Statom

Mathematics Senior Capstone Papers

Mathematicians apply algebraic graph theory to address and interpret problems arising out of data structures and optimization. For example, graph coloring problems have intrigued mathematicians and computer scientists alike. The chromatic polynomial was created to help solve such problems. This research aims to create a greater understanding of the underlying structures behind chromatic polynomials by analyzing the algebraic, deletion-contraction, and color partition methods. Each method has differing applications, but by viewing them all together, this research hopes to show the depth of this most interesting subject in a condensed manner.

Congruences Of The Sums Of The First Rp Fibonacci Numbers, Tyler Warzynak

Mathematics Senior Capstone Papers

This paper serves as an extension/application of a method detailed by Chang et. al. in two separate papers which worked with sums modulo p for combinatorial sequences, positive integers r, and prime numbers p. Using a known formula, the Fibonacci numbers were converted into a sum of binomial coefficients to apply the aforementioned method. A hypothesis was formed using computational methods, where a pattern was observed to hold for the first 50,000 prime numbers. This claim was then proven following the methodology from Chang et. al. using properties of Laurent polynomials, definitions and theorems related to the Fibonacci numbers, and …

Discrete Macaulay-Steiner Geometry, Nikola Kuzmanovski

Dissertations and Doctoral Documents, University of Nebraska-Lincoln, 2023–

This thesis is concerned with discrete isoperimetric inequalities and Hilbert functions. Two generalizations of the Ahlswede-Cai local global principle are presented. These results give positive answers to two questions posed by Harper. One of these results is achieved by proving uniqueness of the lexicographic and colexicographic orders in two dimensions. The other result generalizes the technique which is commonly known as compression and includes almost all previously published results in this direction. The Ahlswede-Cai local global principle is a direct corollary of this result. Optimal downsets are studied in rectangles and triangles. All optimal downsets are found. The main result …

On Generating Bijections For Permutations And Inversion Sequences, Melanie J. Ferreri

Dartmouth College Ph.D Dissertations

Given an algebraic proof of a combinatorial identity, we use recursive methods to construct a bijection demonstrating the identity.

Our first application centers around derangements and nonderangements. A derangement is a permutation with no fixed point, and a nonderangement is a permutation with at least one fixed point. There is a one-term recurrence for the number of derangements of n elements, and we describe a bijective proof of this recurrence which can be found using a recursive map. We then show the combinatorial interpretation of this bijection and how it compares with other known bijections, and show how this extends …

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 …

Strongly I-Bicritical Graphs, Michelle Edwards, Gary Macgillivray, Shahla Nasserasr

Theory & Applications of Graphs

A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown …

The Distinguishing Number Of Some Special Kind Of Graphs, Arti Salat, Amit Sharma

Applications and Applied Mathematics: An International Journal (AAM)

In the present study, the distinguishing number of some different graphs is examined where different graphs like the coconut tree graph, firecracker graph, jellyfish graph, triangular book graph, and banana tree graph have been taken into account. The major goal of the proposed study is to understand the distinguishing number of different graphs for better insights. It is evident from the results that the distinguishing numbers and automorphism groups of the above-mentioned graphs have been carried out successfully.

Some Generalizations Of Corona Product Of Two Graphs, Aparajita Borah, Gajendra Pratap Singh

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we are seeking to conceptualize the notion of corona product of two graphs to contrive some special types of graphs. That is, here our attempt is to regenerate a familiar graph as a product graph. We are considering seven familiar graphs here to reconstruct them with the help of corona product of two graphs. Such types of families of the graphs and operations can be used to study biological pathways as well as to find the optimal order and size for the special types of graphs.