Discrete Mathematics and Combinatorics Commons^™

An Efficient Algorithm To Test Potential Bipartiteness Of Graphical Degree Sequences, Kai Wang

Theory & Applications of Graphs

As a partial answer to a question of Rao, a deterministic and customizable efficient algorithm is presented to test whether an arbitrary graphical degree sequence has a bipartite realization. The algorithm can be configured to run in polynomial time, at the expense of possibly producing an erroneous output on some ``yes'' instances but with very low error rate.

Nilpotent Graph, Dhiren Kumar Basnet, Ajay Sharma, Rahul Dutta

Theory & Applications of Graphs

In this article, we introduce the concept of nilpotent graph of a finite commutative ring. The set of all non nilpotent elements of a ring is taken as the vertex set and two vertices are adjacent if and only if their sum is nilpotent. We discuss some graph theoretic properties of nilpotent graph.

The Integer-Antimagic Spectra Of Graphs With A Chord, Richard M. Low, Dan Roberts, Jinze Zheng

Theory & Applications of Graphs

Let Α be a nontrival abelian group. A connected simple graph G = (V, E) is Α-antimagic if there exists an edge labeling f: E(G) → A \ {0} such that the induced vertex labeling f+: V(G) → Α, defined by f+(v) = Σ_{{uv ∈ E(G)} f(uv), is injective. The integer-antimagic spectrum of a graph G is the set IAM(G) = {k |G is {Ζ}_k-antimagic} and k ≥2. In this paper, we determine the integer-antimagic spectra for cycles with a chord, paths with a chord, and wheels with a chord.

Graph Theoretic Aspects Of Minimum Distance And Equivalence Of Binary Linear Codes, Sudipta Mallik, Bahattin Yildiz

Mathematics Faculty Research

A binary linear [2n, n]-code with generator matrix [I_n|A] can be associated with a digraph on n vertices with adjacency matrix A and vice versa. We use this connection to present a graph theoretic formula for the minimum distance of codes with information rate 1/2. We also formulate the equivalence of such codes via new transformations on corresponding digraphs.

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

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

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

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 …

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 …

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 A_n,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

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 …

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 …

A Gompertz Distribution For Time Scales, Tom Cuchta, Robert Jon Nichel, Sabrina Streipert

Mathematics Faculty Research

We investigate a family of probability distributions, with three parameters associated with the dynamic Gompertz function. We prove its existence for various parameter sets and discuss the existence of its time scale moments. Afterwards, we investigate the special case of discrete time scales, where it is shown that the discrete Gompertz distribution is a q -geometric distribution of the second kind. Further, we find their q -binomial moments, we bound their expected value, and we show how a classical Gompertz distribution is obtained from them.

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 …

Combinatorial Invariants Of Rational Polytopes, Andrés R. Vindas Meléndez

Theses and Dissertations--Mathematics

The first part of this dissertation deals with the equivariant Ehrhart theory of the permutahedron. As a starting point to determining the equivariant Ehrhart theory of the permutahedron, Ardila, Schindler, and I obtain a volume formula for the rational polytopes that are fixed by acting on the permutahedron by a permutation, which generalizes a result of Stanley’s for the volume for the standard permutahedron. Building from the aforementioned work, Ardila, Supina, and I determine the equivariant Ehrhart theory of the permutahedron, thereby resolving an open problem posed by Stapledon. We provide combinatorial descriptions of the Ehrhart quasipolynomial and Ehrhart series …

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 …

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

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 …

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 …

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.

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 f₁ = 1 and f₂ = 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.

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

Graduate Theses, Dissertations, and Problem Reports (ETD)

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 …

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.

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 …

Integer Partitions Under Certain Finiteness Conditions, Tim Wagner

Dissertations, Master's Theses and Master's Reports

This dissertation focuses on problems related to integer partitions under various finiteness restrictions. Much of our work involves the collection of partitions fitting inside a fixed partition $\lambda$, and the associated generating function $G_{\lambda}$.

In Chapter 2, we discuss the flawlessness of such generating functions, as proved by Pouzet using the Multicolor Theorem. We give novel applications of the Multicolor Theorem to re-prove flawlessness of pure $O$-sequences, and show original flawlessness results for other combinatorial sequences. We also present a linear-algebraic generalization of the Multicolor Theorem that may have far-reaching applications.

In Chapter 3, we extend a technique due to …

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.

Heterogeneous Generalizations Of Vertex Coloring, Lucia Ciletti Mazza

Graduate Theses, Dissertations, and Problem Reports (ETD)

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 …

On Coloring Oriented Graphs Of Large Girth, Michael Morris

Graduate Student Theses, Dissertations, & Professional Papers

No abstract provided.

Approximation By The K^Lambda Means Of Fourier Series And Conjugate Series Of Functions In H_{Alpha,P}, Ben Landon, Holly Carley, R. N. Mohapatra

Publications and Research

No abstract provided.

Addendum For The Article Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory & Applications of Graphs

Additional references listed for the article: Saha, Laxman and Basunia, Alamgir Rahaman (2020) "Radio Graceful Labelling of Graphs," Theory and Applications of Graphs: Vol. 7: Iss. 1, Article 7. DOI: 10.20429/tag.2020.070107