Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

1,116 Full-Text Articles 1,296 Authors 292,068 Downloads 114 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

1,116 full-text articles. Page 7 of 44.

Exponents Of Jacobians Of Graphs And Regular Matroids, Hahn Lheem, Deyuan Li, Carl Joshua Quines, Jessica Zhang 2021 Harvard University

Exponents Of Jacobians Of Graphs And Regular Matroids, Hahn Lheem, Deyuan Li, Carl Joshua Quines, Jessica Zhang

Rose-Hulman Undergraduate Mathematics Journal

Let G be a finite undirected multigraph with no self-loops. The Jacobian Jac (G) is a finite abelian group associated with G whose cardinality is equal to the number of spanning trees of G. There are only a finite number of biconnected graphs G such that the exponent of Jac (G) equals 2 or 3. The definition of a Jacobian can also be extended to regular matroids as a generalization of graphs. We prove that there are finitely many connected regular matroids M such that Jac (M) has exponent 2 and characterize all such matroids.


A Card Trick Based On Error-Correcting Codes, Luis A. Perez 2021 California Lutheran University

A Card Trick Based On Error-Correcting Codes, Luis A. Perez

Rose-Hulman Undergraduate Mathematics Journal

Error-correcting codes (ECC), found in coding theory, use methods to handle possible errors that may arise from electronic noise, to a scratch of a CD in a way where they are detected and corrected. Recently, ECC have gone beyond their traditional use. ECC can be used in applications from performing magic tricks to detecting and repairing mutations in DNA sequencing. This paper investigates an application of the Hamming Code, a type of ECC, in the form of a magic trick which uses Andy Liu's description of the Hamming Code through set theory and a known card trick. Finally, connections between …


Mathematical Magic: A Study Of Number Puzzles, Nicasio M. Velez 2021 Maryville College

Mathematical Magic: A Study Of Number Puzzles, Nicasio M. Velez

Rose-Hulman Undergraduate Mathematics Journal

Within this paper, we will briefly review the history of a collection of number puzzles which take the shape of squares, polygons, and polyhedra in both modular and nonmodular arithmetic. Among other results, we develop construction techniques for solutions of both Modulo and regular Magic Squares. For other polygons in nonmodular arithmetic, specifically of order 3, we present a proof of why there are only four Magic Triangles using linear algebra, disprove the existence of the Magic Tetrahedron in two ways, and utilizing the infamous 3-SUM combinatorics problem we disprove the existence of the Magic Octahedron.


Analyzing And Creating Playing Card Cryptosystems, Isaac A. Reiter 2021 Kutztown University of Pennsylvania

Analyzing And Creating Playing Card Cryptosystems, Isaac A. Reiter

Honors Student Research

Before computers, military tacticians and government agents had to rely on pencil-and-paper methods to encrypt information. For agents that want to use low-tech options in order to minimize their digital footprint, non-computerized ciphers are an essential component of their toolbox. Still, the presence of computers limits the pool of effective hand ciphers. If a cipher is not unpredictable enough, then a computer will easily be able to break it. There are 52! ≈ 2^225.58 ways to mix a deck of cards. If each deck order is a key, this means that there are 52! ≈ 2^225.58 different ways to encrypt …


Optimal Tile-Based Dna Self-Assembly Designs For Lattice Graphs And Platonic Solids, Leyda Almodovar, Joanna Ellis-Monaghan, Amanda Harsy, Cory Johnson, Jessica Sorrells 2021 Stonehill College

Optimal Tile-Based Dna Self-Assembly Designs For Lattice Graphs And Platonic Solids, Leyda Almodovar, Joanna Ellis-Monaghan, Amanda Harsy, Cory Johnson, Jessica Sorrells

Mathematics Faculty Publications

A design goal in self-assembly of DNA nanostructures is to find minimal sets of branched junction molecules that will self-assemble into targeted structures. This process can be modeled using techniques from graph theory. This paper is a collection of proofs for a set of DNA complexes which can be represented by specific graphs, namely Platonic solids, square lattice graphs, and triangular lattice graphs. This work supplements the results presented in https://arxiv.org/abs/2108.00035


The Slice Rank Polynomial Method, Thomas C. Martinez 2021 Harvey Mudd College

The Slice Rank Polynomial Method, Thomas C. Martinez

HMC Senior Theses

Suppose you wanted to bound the maximum size of a set in which every k-tuple of elements satisfied a specific condition. How would you go about this? Introduced in 2016 by Terence Tao, the slice rank polynomial method is a recently developed approach to solving problems in extremal combinatorics using linear algebraic tools. We provide the necessary background to understand this method, as well as some applications. Finally, we investigate a generalization of the slice rank, the partition rank introduced by Eric Naslund in 2020, along with various discussions on the intuition behind the slice rank polynomial method and …


Tiling Representations Of Zeckendorf Decompositions, John Lentfer 2021 Claremont Colleges

Tiling Representations Of Zeckendorf Decompositions, John Lentfer

HMC Senior Theses

Zeckendorf’s theorem states that every positive integer can be decomposed uniquely into a sum of non-consecutive Fibonacci numbers (where f1 = 1 and f2 = 2). Previous work by Grabner and Tichy (1990) and Miller and Wang (2012) has found a generalization of Zeckendorf’s theorem to a larger class of recurrent sequences, called Positive Linear Recurrence Sequences (PLRS’s). We apply well-known tiling interpretations of recurrence sequences from Benjamin and Quinn (2003) to PLRS’s. We exploit that tiling interpretation to create a new tiling interpretation specific to PLRS’s that captures the behavior of the generalized Zeckendorf’s theorem.


On Rank-Two And Affine Cluster Algebras, Feiyang Lin 2021 Claremont Colleges

On Rank-Two And Affine Cluster Algebras, Feiyang Lin

HMC Senior Theses

Motivated by existing results about the Kronecker cluster algebra, this thesis is concerned with two families of cluster algebras, which are two different ways of generalizing the Kronecker case: rank-two cluster algebras, and cluster algebras of type An,1. Regarding rank-two cluster algebras, our main result is a conjectural bijection that would prove the equivalence of two combinatorial formulas for cluster variables of rank-two skew-symmetric cluster algebras. We identify a technical result that implies the bijection and make partial progress towards its proof. We then shift gears to study certain power series which arise as limits of ratios of …


Exploring Winning Strategies For The Game Of Cycles, Kailee Lin 2021 Claremont Colleges

Exploring Winning Strategies For The Game Of Cycles, Kailee Lin

HMC Senior Theses

This report details my adventures exploring the Game of Cycles in search of winning strategies. I started by studying combinatorial game theory with hopes to use the Sprague-Grundy Theorem and the structure of Nimbers to gain insight for the Game of Cycles. In the second semester, I pivoted to studying specific types of boards instead. In this thesis I show that variations of the mirror-reverse strategy developed by Alvarado et al. in the original Game of Cycles paper can be used to win on additional game boards with special structure, such as lollipops, steering wheel locks, and 3-spoke trees. Additionally …


Heterogeneous Generalizations Of Vertex Coloring, Lucian Ciletti Mazza 2021 West Virginia University

Heterogeneous Generalizations Of Vertex Coloring, Lucian Ciletti Mazza

Graduate Theses, Dissertations, and Problem Reports

This dissertation proves a collection of results in some heterogeneous generalizations of vertex coloring, i.e. generalizations in which the relationship between the colors of two adjacent vertices may differ throughout the graph. For the most part, the results are from group coloring, group list coloring, and DP coloring. The main results are as follows: a group list coloring analogue of Brooks' Theorem for multigraphs, a result linking group structure (rather than only group size) with group coloring, some results involving coloring edge-disjoint unions, and an examination of the relationship between the group and DP coloring numbers of a multigraph and …


Minimizing Reaction Systems, Matthew R. Thomas 2021 University of North Florida

Minimizing Reaction Systems, Matthew R. Thomas

UNF Graduate Theses and Dissertations

The theoretical model for reaction systems is a relatively new framework originally proposed as a mathematical model for biochemical processes which take place in living cells. Growing interest in this research area has lead to the abstraction of the model for non-biological purpose as well. Reaction systems, with a well understood behavior, have become important for studying transition systems. As with any mathematical model, we want to simplify a given implementation of the model as much as possible while maintaining functional equivalence. This paper discusses the formal model for reaction systems, how we can simplify them with minimization techniques, some …


Cayley Map Embeddings Of Complete Graphs, Miriam Scheinblum 2021 Rollins College

Cayley Map Embeddings Of Complete Graphs, Miriam Scheinblum

Honors Program Theses

This paper looks at Cayley map embeddings of complete graphs on orientable surfaces. Cayley maps constrain graph embeddings to those with cyclical edge rotations, so optimal embeddings on surfaces with the minimum genus may not always be possible. We explore instances when Cayley maps succeed at optimally embedding complete graphs, and when optimal embeddings are not possible, we determine how close to optimal they can get by finding vertex rotations that result in the smallest possible genus. Many of the complete graphs we consider have prime numbers of vertices, so for each complete graph Kn we focus on mappings with …


On Hamilton Cycle Decompositions Of Complete Multipartite Graphs Which Are Both Cyclic And Symmetric, Fatima A. Akinola 2021 Marshall University

On Hamilton Cycle Decompositions Of Complete Multipartite Graphs Which Are Both Cyclic And Symmetric, Fatima A. Akinola

Theses, Dissertations and Capstones

Let G be a graph with v vertices. A Hamilton cycle of a graph is a collection of edges which create a cycle using every vertex. A Hamilton cycle decomposition is cyclic if the set of cycle is invariant under a full length permutation of the vertex set. We say a decomposition is symmetric if all the cycles are invariant under an appropriate power of the full length permutation. Such decompositions are known to exist for complete graphs and families of other graphs. In this work, we show the existence of cyclic n-symmetric Hamilton cycle decompositions of a family …


Counting Conjugacy Classes Of Elements Of Finite Order In Compact Exceptional Groups, Qidong He 2021 Colby College

Counting Conjugacy Classes Of Elements Of Finite Order In Compact Exceptional Groups, Qidong He

Honors Theses

Given a compact exceptional group $G$ and $m,s\in\mathbb{N}$, let $N(G,m)$ be the number of conjugacy classes of elements of order $m$ in $G$, and $N(G,m,s)$ the number of such classes whose elements have $s$ distinct eigenvalues. In string theory, the problem of enumerating certain classes of vacua in the string landscape can be rephrased in terms of the study of these quantities. We develop unified combinatorial algorithms based on Burnside's Lemma that can be used to compute both quantities for each of the five compact exceptional groups. Thus, we provide a combinatorial, alternative method to that of Djoković and extend …


On The Ranks Of String C-Group Representations For Symplectic And Orthogonal Groups, Peter A. Brooksbank 2021 Bucknell University

On The Ranks Of String C-Group Representations For Symplectic And Orthogonal Groups, Peter A. Brooksbank

Faculty Journal Articles

We determine the ranks of string C-group representations of the groups PSp(4,q)=Ω(5,q), and comment on those of higher-dimensional symplectic and orthogonal groups.


Algebraic, Analytic, And Combinatorial Properties Of Power Product Expansions In Two Independent Variables., Mohamed Ammar Elewoday 2021 West Virginia University

Algebraic, Analytic, And Combinatorial Properties Of Power Product Expansions In Two Independent Variables., Mohamed Ammar Elewoday

Graduate Theses, Dissertations, and Problem Reports

Let $F(x,y)=I+\hspace{-.3cm}\sum\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}A_{m,n}x^my^n$ be a formal power series, where the coefficients $A_{m,n}$ are either all matrices or all scalars. We expand $F(x,y)$ into the formal products $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I+G_{m,n}x^m y^n)$, $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I-H_{m,n}x^m y^n)^{-1}$, namely the \textit{ power product expansion in two independent variables} and \textit{inverse power product expansion in two independent variables} respectively. By developing new machinery involving the majorizing infinite product, we provide estimates on the domain of absolute convergence of the infinite product via the Taylor series coefficients of $F(x,y)$. This machinery introduces a myriad of "mixed expansions", uncovers various algebraic connections between the $(A_{m,n})$ and the $(G_{m,n})$, and uncovers various algebraic …


An Enumeration Of Nested Networks, Nathan Cornelius 2021 The University of Akron

An Enumeration Of Nested Networks, Nathan Cornelius

Williams Honors College, Honors Research Projects

Nested networks have several applications in phylogenetics and electrical circuit theory. In many cases, there may exist more than one distinct network which correctly models a given data set. This proposes a combinatorial problem to determine all possible network solutions. In this paper, we partially solve this problem by developing exponential generating functions which enumerate all 1-nested and 2-nested unicyclic networks. We also describe our procedure to directly count all 1-nested and 2-nested networks and provide all 1-nested networks with 7, 8, and 9 terminal nodes.


Exploring Plane Partitions, Nicholas Heim 2021 The University of Akron

Exploring Plane Partitions, Nicholas Heim

Williams Honors College, Honors Research Projects

The combinatorial theory of partitions has a number of applications including the representation theory of the symmetric group. A particularly important result counts the number of standard Young tableau of a given partition in terms of the hook lengths of the partition. In this paper we explore the analog of the hook length formula for plane partitions, the three-dimensional analog of ordinary partitions. We show that equality does not always hold but we conjecture that a certain inequality holds. Using a computer program, we verify this conjectured inequality for all 1982 plane partitions up to n = 11.


Major Index Over Descent Distributions Of Standard Young Tableaux, Emily Anible 2021 Michigan Technological University

Major Index Over Descent Distributions Of Standard Young Tableaux, Emily Anible

Dissertations, Master's Theses and Master's Reports

This thesis concerns the generating functions $f_{\lambda, k}(q)$ for standard Young tableaux of shape $\lambda$ with precisely $k$ descents, aiming to find closed formulas for a general form given by Kirillov and Reshetikhin in 1988. Throughout, we approach various methods by which further closed forms could be found. In Chapter 2 we give closed formulas for tableaux of any shape and minimal number of descents, which arise as principal specializations of Schur functions. We provide formulas for tableaux with three parts and one more than minimal number of descents, and demonstrate that the technique is extendable to any number of …


A Tropical Approach To The Brill-Noether Theory Over Hurwitz Spaces, Kaelin Cook-Powell 2021 University of Kentucky

A Tropical Approach To The Brill-Noether Theory Over Hurwitz Spaces, Kaelin Cook-Powell

Theses and Dissertations--Mathematics

The geometry of a curve can be analyzed in many ways. One way of doing this is to study the set of all divisors on a curve of prescribed rank and degree, known as a Brill-Noether variety. A sequence of results, starting in the 1980s, answered several fundamental questions about these varieties for general curves. However, many of these questions are still unanswered if we restrict to special families of curves. This dissertation has three main goals. First, we examine Brill-Noether varieties for these special families and provide combinatorial descriptions of their irreducible components. Second, we provide a natural generalization …


Digital Commons powered by bepress