Discrete Mathematics and Combinatorics Commons^™

On The Number Of Ways To Express A Set As A Union Of Individually Interesting Sets, Alison Watson

Master's Theses

In a dataset that contains what ought rightly to be several distinct datasets placed in juxtaposition with each other, grouping datapoints based on observed similarities can be done in many ways. Topological Data Analysis (TDA) is a field of math that seeks to impose geometric structure onto datasets, thereby translating problems in statistics to problems in geometry or topology. A common truism in this field is “Data has shape and shape has meaning.” In this thesis, we use combinatorial and categorical arguments to demonstrate some shortcomings of a TDA approach on a class of inverse problems inspired by marine wildlife …

Catalan And Hyper-Catalan Numbers: Combinatorial Applications To Polynomial Equations, Leilani Natale

Williams Honors College, Honors Research Projects

In this paper, we study Catalan numbers and their generalization, hyper-Catalan numbers, and explore how these sequences arise naturally in the context of solving polynomial equations using infinite power series. We begin by introducing the Catalan numbers through their combinatorial interpretation as triangulations of convex polygons. Using this geometric definition, we derive a relation whose recursive structure leads to a quadratic functional equation. Interpreting this relation as a formal power series equation allows us to express solutions to quadratic equations as infinite power series whose coefficients are given by the Catalan numbers. This framework is then extended by allowing polygon …

Incremental Increases Between Successive Integers When Raised To The Nth Power, Sutton J. Olesen

Rose-Hulman Undergraduate Mathematics Journal

For thousands of years, the beautiful field of number theory has captivated mathematicians with its elegant simplicity. Positive integers continue to reveal properties and relationships that are a joy to uncover, and in this paper, we investigate a pattern involving exponents and factorials while exploring some common notations in the field of number theory. Combinatorics, the field dealing with the mathematics of counting and arranging, also holds a presence in this paper. Pascal’s Triangle–the foundation of binomial expressions, also comes into play due to its tight relationship with combinatorics. Pascal’s Identity, the property that builds the triangle, becomes very useful …

Construction Techniques For Linear Realizations Of Multisets With Small Support, M. A. Ollis

Emerson Authors, Researchers, & Creators

The Buratti-Horak Rosa Conjecture is a problem in graph theory asking when we can find a Hamiltonian path in the complete graph that has various properties to do with edge lengths. In this paper, we use constructive methods to show that the conjecture is true for various parameter sets where it was previously unknown.

The Combinatorics Of Integer Partitions Enumerated By Some Exotic Weights, Hunter Waldron

Dissertations, Master's Theses and Master's Reports

Identities of integer partitions generally state that two dissimilar appearing families of partitions are in fact equinumerous when both are restricted to any fixed size. Euler's theorem is a classic example of such an identity, which equates the number of partitions with odd parts to the number of partitions with distinct parts. Lately, analogs of known partition identities involving weights other than size have begun to attract research interest. This dissertation is an investigation of two such weights. In Chapter 2, we study Schmidt weights, which count only parts with indices belonging to some given subset of the positive integers. …

Counting The Classes Of Projectively-Equivalent Pentagons On Finite Projective Planes Of Prime Order, Maxwell Hosler

Rose-Hulman Undergraduate Mathematics Journal

In this paper, we examine the number of equivalence classes of pentagons on finite projective planes of prime order under projective transformations. We are interested in those pentagons in general position, meaning that no three vertices are collinear. We consider those planes which can be constructed from finite fields of prime order, and use algebraic techniques to characterize them by their symmetries. We are able to construct a unique representative for each pentagon class with nontrivial symmetries. We can then leverage this fact to count classes of pentagons in general. We discover that there are (1/10)((p+3)(p-3)+4 …

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 …

Optimizing Buying Strategies In Dominion, Nikolas A. Koutroulakis

Rose-Hulman Undergraduate Mathematics Journal

Dominion is a deck-building card game that simulates competing lords growing their kingdoms. Here we wish to optimize a strategy called Big Money by modeling the game as a Markov chain and utilizing the associated transition matrices to simulate the game. We provide additional analysis of a variation on this strategy known as Big Money Terminal Draw. Our results show that player's should prioritize buying provinces over improving their deck. Furthermore, we derive heuristics to guide a player's decision making for a Big Money Terminal Draw Deck. In particular, we show that buying a second Smithy is always more optimal …

Seating Groups And 'What A Coincidence!': Mathematics In The Making And How It Gets Presented, Peter J. Rowlett

Journal of Humanistic Mathematics

Mathematics is often presented as a neatly polished finished product, yet its development is messy and often full of mis-steps that could have been avoided with hindsight. An experience with a puzzle illustrates this conflict. The puzzle asks for the probability that a group of four and a group of two are seated adjacently within a hundred seats, and is solved using combinatorics techniques.

Enumeration Of Increasing Trees, Garrett M. Southwood

Honors College Theses

We consider the generating function for increasingly labelled trees. By generalizing the proof through symbolic method, we are able to study various statistics regarding binary increasing trees with respect to height restrictions. We then apply our approach to special colorings of increasing trees in order to obtain their generating functions and, from there, derive the counting sequence for (ak+a)-colored recursive trees. We also present some interesting bijections between colored and non-colored increasing trees.

Slₖ-Tilings And Paths In ℤᵏ, Zachery T. Peterson

Theses and Dissertations--Mathematics

An SLₖ-frieze is a bi-infinite array of integers where adjacent entries satisfy a certain diamond rule. SL₂-friezes were introduced and studied by Conway and Coxeter. Later, these were generalized to infinite matrix-like structures called tilings as well as higher values of k. A recent paper by Short showed a bijection between bi-infinite paths of reduced rationals in the Farey graph and SL₂-tilings. We extend this result to higher k by constructing a bijection between SLₖ-tilings and certain pairs of bi-infinite strips of vectors in ℤᵏ called paths. The key ingredient in the proof is the relation to Plucker friezes and …

Enumeration Of Lattice Paths With Restrictions, Vince White

College of Graduate Studies: Theses & Dissertations

Lattice path enumeration, through the lens of Catalan numbers, plays a crucial role in combinatorics. This thesis delves into enumerations of some of the most common lattice paths – north-east paths, up-down paths, and Dyck paths – with restrictions applied. The first restriction is counting north-east lattice paths that only cross the diagonal line, y=x, once. The second form of lattice paths with restrictions is up-down paths that cross the x-axis exactly once and fall to a fixed depth of k. While working through this module, a novel proof for a known integer sequence was used, then applied to generate …

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.

On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak

Theory & Applications of Graphs

The Balanced Connected Subgraph problem (BCS) was introduced by Bhore et al. In the BCS problem we are given a vertex-colored graph G = (V, E) where each vertex is colored “red” or “blue”. The goal is to find a maximum cardinality induced connected subgraph H of G such that H contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as many special classes of graphs. In this work we explore the time complexity of the BCS problem in case of regular graphs. We prove that the BCS …

Staircase Packings Of Integer Partitions, Melody Arteaga

Mathematics, Statistics, and Computer Science Honors Projects

An integer partition is a weakly decreasing sequence of positive integers. We study the family of packings of integer partitions in the triangular array of size n, where successive partitions in the packings are separated by at least one zero. We prove that these are enumerated by the Bell-Like number sequence (OEIS A091768), and investigate its many recursive properties. We also explore their poset (partially ordered set) structure. Finally, we characterize various subfamilies of these staircase packings, including one restriction that connects back to the original patterns of the whole family.

An Inquiry Into Lorentzian Polynomials, Tomás Aguilar-Fraga

HMC Senior Theses

In combinatorics, it is often desirable to show that a sequence is unimodal. One method of establishing this is by proving the stronger yet easier-to-prove condition of being log-concave, or even ultra-log-concave. In 2019, Petter Brändén and June Huh introduced the concept of Lorentzian polynomials, an exciting new tool which can help show that ultra-log-concavity holds in specific cases. My thesis investigates these Lorentzian polynomials, asking in which situations they are broadly useful. It covers topics such as matroid theory, discrete convexity, and Mason’s conjecture, a long-standing open problem in matroid theory. In addition, we discuss interesting applications to known …

Minimal Sets, Union-Closed Families, And Frankl's Conjecture, Christopher S. Flippen

Theses and Dissertations

The most common statement of Frankl's conjecture is that for every finite family of sets closed under the union operation, there is some element which belongs to at least half of the sets in the family. Despite its apparent simplicity, Frankl's conjecture has remained open and highly researched since its first mention in 1979. In this paper, we begin by examining the history and previous attempts at solving the conjecture. Using these previous ideas, we introduce the concepts of minimal sets and minimally-generated families, some ideas related to viewing union-closed families as posets, and some constructions of families involving poset-defined …

Counting Spanning Trees On Triangular Lattices, Angie Wang

CMC Senior Theses

This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …

Characterizations Of Certain Classes Of Graphs And Matroids, Jagdeep Singh

LSU Doctoral Dissertations

``If a theorem about graphs can be expressed in terms of edges and cycles only, it probably exemplifies a more general theorem about matroids." Most of my work draws inspiration from this assertion, made by Tutte in 1979.

In 2004, Ehrenfeucht, Harju and Rozenberg proved that all graphs can be constructed from complete graphs via a sequence of the operations of complementation, switching edges and non-edges at a vertex, and local complementation. In Chapter 2, we consider the binary matroid analogue of each of these graph operations. We prove that the analogue of the result of Ehrenfeucht et. al. does …

Vertex Identification In Graphs, Yuya Kono

Dissertations

In recent decades, there has been increased interest in studying ways touniquely identify the vertices of a given graph. Two of best-known vertex identification methods are referred to as the metric dimension introduced by Slater and by Harary, and Melter in the1970s, and the partition dimension introduced by Chartrand in 2000. The first method deals with locating an ordered set of vertices in a connected graph G and uniquely identifying each vertex of G by means of the distance between this vertex and the vertices in the ordered set. The second method deals with partitioning the vertex set of a …

Multicolor Ramsey And List Ramsey Numbers For Double Stars, Jake Ruotolo

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For a graph H, the k-color Ramsey number r(H; k) of H is the smallest integer n such that every k-edge-coloring of K_n contains a monochromatic copy of H. Despite active research for decades, very little is known about Ramsey numbers of graphs. This is especially true for r(H; k) when k is at least 3, also known as the multicolor Ramsey number of …

Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler

Graduate Student Theses, Dissertations, & Professional Papers

In this study we present a novel algorithm, LASSO, for solving the unbounded and bounded subset sum problem. The LASSO algorithm was designed to solve the unbounded SSP quickly and to return all subsets summing to a target sum. As speed was the highest priority, we benchmarked the run time performance of LASSO against implementations of some common approaches to the bounded SSP, as well as the only comparable implementation for solving the unbounded SSP that we could find. In solving the bounded SSP, our algorithm had a significantly faster run time than the competing algorithms when the target sum …

Partial Representations For Ternary Matroids, Ebony Perez

Electronic Theses, Projects, and Dissertations

In combinatorics, a matroid is a discrete object that generalizes various notions of dependence that arise throughout mathematics. All of the information about some matroids can be encoded (or represented) by a matrix whose entries come from a particular field, while other matroids cannot be represented in this way. However, for any matroid, there exists a matrix, called a partial representation of the matroid, that encodes some of the information about the matroid. In fact, a given matroid usually has many different partial representations, each providing different pieces of information about the matroid. In this thesis, we investigate when a …

From Multi-Prime To Subset Labelings Of Graphs, Bethel I. Mcgrew

Dissertations

A graph labeling is an assignment of labels (elements of some set) to the vertices or edges (or both) of a graph G. If only the vertices of G are labeled, then the resulting graph is a vertex-labeled graph. If only the edges are labeled, the resulting graph is an edge-labeled graph. The concept was first introduced in the 19th century when Arthur Cayley established Cayley’s Tree Formula, which proved that there are n^n-2 distinct labeled trees of order n. Since then, it has grown into a popular research area.

In this study, we first review several types …

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.

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.

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 …

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.

The Name Tag Problem, Christian Carley

Rose-Hulman Undergraduate Mathematics Journal

The Name Tag Problem is a thought experiment that, when formalized, serves as an introduction to the concept of an orthomorphism of $\Zn$. Orthomorphisms are a type of group permutation and their graphs are used to construct mutually orthogonal Latin squares, affine planes and other objects. This paper walks through the formalization of the Name Tag Problem and its linear solutions, which center around modular arithmetic. The characterization of which linear mappings give rise to these solutions developed in this paper can be used to calculate the exact number of linear orthomorphisms for any additive group Z/nZ, which is demonstrated …

Investigating First Returns: The Effect Of Multicolored Vectors, Shakuan Frankson, Myka Terry

Rose-Hulman Undergraduate Mathematics Journal

By definition, a first return is the immediate moment that a path, using vectors in the Cartesian plane, touches the x-axis after leaving it previously from a given point; the initial point is often the origin. In this case, using certain diagonal and horizontal vectors while restricting the movements to the first quadrant will cause almost every first return to end at the point (2n,0), where 2n counts the equal number of up and down steps in a path. The exception will be explained further in the sections below. Using the first returns of Catalan, Schröder, and Motzkin numbers, which …