Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Algebra (54)
- Computer Sciences (35)
- Geometry and Topology (30)
- Other Mathematics (30)
- Applied Mathematics (27)
-
- Theory and Algorithms (25)
- Number Theory (20)
- Algebraic Geometry (18)
- Other Applied Mathematics (16)
- Statistics and Probability (13)
- Analysis (10)
- Artificial Intelligence and Robotics (8)
- Engineering (8)
- Life Sciences (8)
- Probability (7)
- Set Theory (7)
- Genetics and Genomics (5)
- Harmonic Analysis and Representation (5)
- Numerical Analysis and Computation (5)
- Numerical Analysis and Scientific Computing (5)
- Physics (5)
- Arts and Humanities (4)
- Computational Biology (4)
- Ordinary Differential Equations and Applied Dynamics (4)
- Applied Statistics (3)
- Bioinformatics (3)
- Data Science (3)
- Institution
-
- East Tennessee State University (53)
- Claremont Colleges (44)
- University of Kentucky (32)
- Georgia Southern University (18)
- Louisiana State University (15)
-
- California State University, San Bernardino (14)
- Virginia Commonwealth University (13)
- West Virginia University (11)
- Western University (10)
- Michigan Technological University (9)
- Western Michigan University (9)
- City University of New York (CUNY) (7)
- University of Massachusetts Amherst (7)
- University of Tennessee, Knoxville (7)
- Bard College (6)
- The University of Akron (6)
- California Polytechnic State University, San Luis Obispo (5)
- Marshall University (5)
- University of Nevada, Las Vegas (5)
- University of North Florida (5)
- Clemson University (4)
- Missouri State University (4)
- Murray State University (4)
- The College of Wooster (4)
- William & Mary (4)
- Boise State University (3)
- Rollins College (3)
- University of Central Florida (3)
- University of Louisville (3)
- University of New Orleans (3)
- Keyword
-
- Graph theory (56)
- Combinatorics (35)
- Graph Theory (12)
- Graph (10)
- Graphs (10)
-
- Mathematics (10)
- Domination (9)
- Graph coloring (7)
- Combinatorial analysis (6)
- Matroids (6)
- Permutations (6)
- Connectivity (5)
- Group theory (5)
- Partitions (5)
- Polytopes (5)
- Poset (5)
- Academic -- UNF -- Master of Science in Mathematical Science; Dissertations (4)
- Algebra (4)
- Chromatic number (4)
- Covering (4)
- Coverings (4)
- Cryptography (4)
- Discrete mathematics (4)
- Packings (4)
- Thesis; University of North Florida; UNF; Dissertations (4)
- Topological graph theory (4)
- Algorithm (3)
- Bioinformatics (3)
- Combinatorial optimization (3)
- Complementary prism (3)
- Publication Year
- Publication
-
- Electronic Theses and Dissertations (72)
- HMC Senior Theses (38)
- Theses and Dissertations--Mathematics (29)
- Theses and Dissertations (16)
- LSU Doctoral Dissertations (15)
-
- Doctoral Dissertations (12)
- Electronic Theses, Projects, and Dissertations (12)
- Graduate Theses, Dissertations, and Problem Reports (11)
- Electronic Thesis and Dissertation Repository (10)
- Dissertations, Master's Theses and Master's Reports (9)
- Honors Theses (9)
- Dissertations, Theses, and Capstone Projects (7)
- Dissertations (6)
- Williams Honors College, Honors Research Projects (6)
- Theses, Dissertations and Capstones (5)
- UNF Graduate Theses and Dissertations (5)
- UNLV Theses, Dissertations, Professional Papers, and Capstones (5)
- Undergraduate Honors Theses (5)
- Honors College Theses (4)
- MSU Graduate Theses (4)
- Senior Independent Study Theses (4)
- CMC Senior Theses (3)
- Honors Program Theses (3)
- Honors Undergraduate Theses (3)
- Master's Theses (3)
- University of New Orleans Theses and Dissertations (3)
- All Dissertations (2)
- All Graduate Theses and Dissertations, Spring 1920 to Summer 2023 (2)
- All Theses (2)
- Boise State University Theses and Dissertations (2)
Articles 1 - 30 of 359
Full-Text Articles in Discrete Mathematics and Combinatorics
The Modular Generalized Springer Correspondence For The Symplectic Group, Joseph Dorta
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 …
Counting Conjugates Of Colored Compositions, Jesus Omar Sistos Barron
Counting Conjugates Of Colored Compositions, Jesus Omar Sistos Barron
Honors College Theses
The properties of n-color compositions have been studied parallel to those of regular compositions. The conjugate of a composition as defined by MacMahon, however, does not translate well to n-color compositions, and there is currently no established analogous concept. We propose a conjugation rule for cyclic n-color compositions. We also count the number of self-conjugates under these rules and establish a couple of connections between these and regular compositions.
Graph Coloring Reconfiguration, Reem Mahmoud
Graph Coloring Reconfiguration, Reem Mahmoud
Theses and Dissertations
Reconfiguration is the concept of moving between different solutions to a problem by transforming one solution into another using some prescribed transformation rule (move). Given two solutions s1 and s2 of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s1 into s2. Reconfiguration is an area of research with many contributions towards various fields such as mathematics and computer science.
The k-coloring reconfiguration problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type …
Problems In Chemical Graph Theory Related To The Merrifield-Simmons And Hosoya Topological Indices, William B. O'Reilly
Problems In Chemical Graph Theory Related To The Merrifield-Simmons And Hosoya Topological Indices, William B. O'Reilly
Electronic Theses and Dissertations
In some sense, chemical graph theory applies graph theory to various physical sciences. This interdisciplinary field has significant applications to structure property relationships, as well as mathematical modeling. In particular, we focus on two important indices widely used in chemical graph theory, the Merrifield-Simmons index and Hosoya index. The Merrifield-Simmons index and the Hosoya index are two well-known topological indices used in mathematical chemistry for characterizing specific properties of chemical compounds. Substantial research has been done on the two indices in terms of enumerative problems and extremal questions. In this thesis, we survey known extremal results and consider the generalized …
Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham
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.
Foundations Of Memory Capacity In Models Of Neural Cognition, Chandradeep Chowdhury
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 …
A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu
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 …
Zero-Knowledge Reductions And Confidential Arithmetic, Marvin Jones
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:
- Provide a thorough survey in a variety of zero-knowledge techniques and protocols.
- 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
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 …
Intersection Cohomology Of Rank One Local Systems For Arrangement Schubert Varieties, Shuo Lin
Intersection Cohomology Of Rank One Local Systems For Arrangement Schubert Varieties, Shuo Lin
Doctoral Dissertations
In this thesis we study the intersection cohomology of arrangement Schubert varieties with coefficients in a rank one local system on a hyperplane arrangement complement. We prove that the intersection cohomology can be computed recursively in terms of certain polynomials, if a local system has only $\pm 1$ monodromies. In the case where the hyperplane arrangement is generic central or equivalently the associated matroid is uniform and the local system has only $\pm 1$ monodromies, we prove that the intersection cohomology is a combinatorial invariant. In particular when the hyperplane arrangement is associated to the uniform matroid of rank $n-1$ …
Facets Of The Union-Closed Polytope, Daniel Gallagher
Facets Of The Union-Closed Polytope, Daniel Gallagher
Doctoral Dissertations
In the haze of the 1970s, a conjecture was born to unknown parentage...the union-closed sets conjecture. Given a family of sets $\FF$, we say that $\FF$ is union-closed if for every two sets $S, T \in \FF$, we have $S \cup T \in \FF$. The union-closed sets conjecture states that there is an element in at least half of the sets of any (non-empty) union-closed family. In 2016, Pulaj, Raymond, and Theis reinterpreted the conjecture as an optimization problem that could be formulated as an integer program. This thesis is concerned with the study of the polytope formed by taking …
On The Order-Type Complexity Of Words, And Greedy Sidon Sets For Linear Forms, Yin Choi Cheng
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, …
Fuglede's Conjecture In Some Finite Abelian Groups, Thomas Fallon
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.
Generating Polynomials Of Exponential Random Graphs, Mohabat Tarkeshian
Generating Polynomials Of Exponential Random Graphs, Mohabat Tarkeshian
Electronic Thesis and Dissertation Repository
The theory of random graphs describes the interplay between probability and graph theory: it is the study of the stochastic process by which graphs form and evolve. In 1959, Erdős and Rényi defined the foundational model of random graphs on n vertices, denoted G(n, p) ([ER84]). Subsequently, Frank and Strauss (1986) added a Markov twist to this story by describing a topological structure on random graphs that encodes dependencies between local pairs of vertices ([FS86]). The general model that describes this framework is called the exponential random graph model (ERGM).
In the past, determining when a probability distribution has strong …
Signings Of Graphs And Sign-Symmetric Signed Graphs, Ahmad Asiri
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
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
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 …
Representations From Group Actions On Words And Matrices, Joel T. Anderson
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
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 …
Complex-Valued Approach To Kuramoto-Like Oscillators, Jacqueline Bao Ngoc Doan
Complex-Valued Approach To Kuramoto-Like Oscillators, Jacqueline Bao Ngoc Doan
Electronic Thesis and Dissertation Repository
The Kuramoto Model (KM) is a nonlinear model widely used to model synchrony in a network of oscillators – from the synchrony of the flashing fireflies to the hand clapping in an auditorium. Recently, a modification of the KM (complex-valued KM) was introduced with an analytical solution expressed in terms of a matrix exponential, and consequentially, its eigensystem. Remarkably, the analytical KM and the original KM bear significant similarities, even with phase lag introduced, despite being determined by distinct systems. We found that this approach gives a geometric perspective of synchronization phenomena in terms of complex eigenmodes, which in turn …
Cohen-Macaulay Properties Of Closed Neighborhood Ideals, Jackson Leaman
Cohen-Macaulay Properties Of Closed Neighborhood Ideals, Jackson Leaman
All Theses
This thesis investigates Cohen-Macaulay properties of squarefree monomial ideals, which is an important line of inquiry in the field of combinatorial commutative algebra. A famous example of this is Villareal’s edge ideal [11]: given a finite simple graph G with vertices x1, . . . , xn, the edge ideal of G is generated by all the monomials of the form xixj where xi and xj are adjacent in G. Villareal’s characterization of Cohen-Macaulay edge ideals associated to trees is an often-cited result in the literature. This was extended to chordal and bipartite graphs by Herzog, Hibi, and Zheng in …
Roots Of Quaternionic Polynomials And Automorphisms Of Roots, Olalekan Ogunmefun
Roots Of Quaternionic Polynomials And Automorphisms Of Roots, Olalekan Ogunmefun
Electronic Theses and Dissertations
The quaternions are an extension of the complex numbers which were first described by Sir William Rowan Hamilton in 1843. In his description, he gave the equation of the multiplication of the imaginary component similar to that of complex numbers. Many mathematicians have studied the zeros of quaternionic polynomials. Prominent of these, Ivan Niven pioneered a root-finding algorithm in 1941, Gentili and Struppa proved the Fundamental Theorem of Algebra (FTA) for quaternions in 2007. This thesis finds the zeros of quaternionic polynomials using the Fundamental Theorem of Algebra. There are isolated zeros and spheres of zeros. In this thesis, we …
Automorphisms Of A Generalized Quadrangle Of Order 6, Ryan Pesak
Automorphisms Of A Generalized Quadrangle Of Order 6, Ryan Pesak
Undergraduate Honors Theses
In this thesis, we study the symmetries of the putative generalized quadrangle of order 6. Although it is unknown whether such a quadrangle Q can exist, we show that if it does, that Q cannot be transitive on either points or lines. We first cover the background necessary for studying this problem. Namely, the theory of groups and group actions, the theory of generalized quadrangles, and automorphisms of GQs. We then prove that a generalized quadrangle Q of order 6 cannot have a point- or line-transitive automorphism group, and we also prove that if a group G acts faithfully on …
Reverse Mathematics Of Ramsey's Theorem, Nikolay Maslov
Reverse Mathematics Of Ramsey's Theorem, Nikolay Maslov
Electronic Theses, Projects, and Dissertations
Reverse mathematics aims to determine which set theoretic axioms are necessary to prove the theorems outside of the set theory. Since the 1970’s, there has been an interest in applying reverse mathematics to study combinatorial principles like Ramsey’s theorem to analyze its strength and relation to other theorems. Ramsey’s theorem for pairs states that for any infinite complete graph with a finite coloring on edges, there is an infinite subset of nodes all of whose edges share one color. In this thesis, we introduce the fundamental terminology and techniques for reverse mathematics, and demonstrate their use in proving Kőnig's lemma …
Matroid Generalizations Of Some Graph Results, Cameron Crenshaw
Matroid Generalizations Of Some Graph Results, Cameron Crenshaw
LSU Doctoral Dissertations
The edges of a graph have natural cyclic orderings. We investigate the matroids for which a similar cyclic ordering of the circuits is possible. A full characterization of the non-binary matroids with this property is given. Evidence of the difficulty of this problem for binary matroids is presented, along with a partial result for binary orderable matroids.
For a graph G, the ratio of |E(G)| to the minimum degree of G has a natural lower bound. For a matroid M that is representable over a finite field, we generalize this to a lower bound on …
Irregular Domination In Graphs, Caryn Mays
Irregular Domination In Graphs, Caryn Mays
Dissertations
Domination in graphs has been a popular area of study due in large degree to its applications to modern society as well as the mathematical beauty of the topic. While this area evidently began with the work of Claude Berge in 1958 and Oystein Ore in 1962, domination did not become an active area of research until 1977 with the appearance of a survey paper by Ernest Cockayne and Stephen Hedetniemi. Since then, a large number of variations of domination have surfaced and provided numerous applications to different areas of science and real-life problems. Among these variations are domination parameters …
Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon
Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon
Senior Theses
This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.
Zonality In Graphs, Andrew Bowling
Zonality In Graphs, Andrew Bowling
Dissertations
Graph labeling and coloring are among the most popular areas of graph theory due to both the mathematical beauty of these subjects as well as their fascinating applications. While the topic of labeling vertices and edges of graphs has existed for over a century, it was not until 1966 when Alexander Rosa introduced a labeling, later called a graceful labeling, that brought the area of graph labeling to the forefront in graph theory. The subject of graph colorings, on the other hand, goes back to 1852 when the young British mathematician Francis Guthrie observed that the countries in a map …
A Stronger Strong Schottky Lemma For Euclidean Buildings, Michael E. Ferguson
A Stronger Strong Schottky Lemma For Euclidean Buildings, Michael E. Ferguson
Dissertations, Theses, and Capstone Projects
We provide a criterion for two hyperbolic isometries of a Euclidean building to generate a free group of rank two. In particular, we extend the application of a Strong Schottky Lemma to buildings given by Alperin, Farb and Noskov. We then use this extension to obtain an infinite family of matrices that generate a free group of rank two. In doing so, we also introduce an algorithm that terminates in finite time if the lemma is applicable for pairs of certain kinds of matrices acting on the Euclidean building for the special linear group over certain discretely valued fields.
Methods Of Computing Graph Gonalities, Noah Speeter
Methods Of Computing Graph Gonalities, Noah Speeter
Theses and Dissertations--Mathematics
Chip firing is a category of games played on graphs. The gonality of a graph tells us how many chips are needed to win one variation of the chip firing game. The focus of this dissertation is to provide a variety of new strategies to compute the gonality of various graph families. One family of graphs which this dissertation is particularly interested in is rook graphs. Rook graphs are the Cartesian product of two or more complete graphs and we prove that the gonality of two dimensional rook graphs is the expected value of (n − 1)m where n is …