Discrete Mathematics and Combinatorics Commons^™

Characterizing 2-Trees Relative To Chordal And Series-Parallel Graphs, Terry A. Mckee

Theory and Applications of Graphs

The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as the edge-maximal series-parallel graphs. These are also precisely the 2-connected graphs that are simultaneously chordal and series-parallel, where these latter two better-known types of graphs have themselves been both characterized and applied in numerous ways that are unmotivated by their interaction with 2-trees and with each other.

Toward providing such motivation, the …

Innovative Approach To Solving Combinatic Elements And Some Problems Of Newton Binomy In School Mathematics Course, Nilufar Okbayeva

Central Asian Problems of Modern Science and Education

This article provides information on the elements of combinatorics in the school mathematics course and solutions to some problems related to the Newtonian binomial. This article is also aimed at solving problems related to the indepth study of the elements of combinatorics in the school course, the creation of a sufficient basis for the study of probability theory and mathematical statistics in the future.

Skolem Number Of Subgraphs On The Triangular Lattice, Braxton Carrigan, Garrett Green

Communications on Number Theory and Combinatorial Theory

A Skolem sequence can be thought of as a labelled path where any two vertices with the same label are that distance apart. This concept has naturally been generalized to graph labelling. This brings rise to the question; “what is the smallest set of consecutive positive integers we can use to properly Skolem label a graph?” This is known as the Skolem number of the graph. In this paper we give the Skolem number for three natural vertex induced subgraphs of the triangular lattice graph.

Connectivity Of Matroids And Polymatroids, Zachary R. Gershkoff

LSU Doctoral Dissertations

This dissertation is a collection of work on matroid and polymatroid connectivity. Connectivity is a useful property of matroids that allows a matroid to be decomposed naturally into its connected components, which are like blocks in a graph. The Cunningham-Edmonds tree decomposition further gives a way to decompose matroids into 3-connected minors. Much of the research below concerns alternate senses in which matroids and polymatroids can be connected. After a brief introduction to matroid theory in Chapter 1, the main results of this dissertation are given in Chapters 2 and 3. Tutte proved that, for an element e of a …

Determining Biases In The Card-Chameleon Cryptosystem, Isaac Reiter, Eric Landquist

Communications on Number Theory and Combinatorial Theory

Throughout history, spies, soldiers, and others have relied on so-called {\em hand ciphers} to send encrypted messages. Since the creation of Pontifex (also known as Solitaire) by Bruce Schneier in 1999, a number of hand ciphers utilizing a standard deck of playing cards have emerged. Since there are $52! \approx 2^{225.58}$ possible ways to order a deck of cards, there are over 225 bits of entropy in a well-shuffled deck of cards. Theoretically, this can provide enough security to rival modern computer-based cryptosystems. In this paper, we describe and analyze one such playing card cipher, Card-Chameleon, created by Matthew McKague. …

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

Theory and 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 and 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 and 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.

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 …

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

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 …

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 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 …

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 …

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 …

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 …