Mathematics Commons^™

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

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

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 …

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.

Exploring The Structure Of Partial Difference Sets With Denniston Parameters, Nicolas Ferree

Honors Theses

In this work, we investigate the structure of particular partial difference sets (PDS) of size 70 with Denniston parameters in an elementary abelian group and in a nonelementary abelian group. We will make extensive use of character theory in our investigation and ultimately seek to understand the nature of difference sets with these parameters. To begin, we will cover some basic definitions and examples of difference sets and partial difference sets. We will then move on to some basic theorems about partial difference sets before introducing a group ring formalism and using it to explore several important constructions of partial …

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 …

Parking Garage Functions, Felicia Elizabeth Flores

Senior Projects Spring 2023

Senior Project submitted to The Division of Science, Mathematics and Computing of Bard College.

This project is about a generalization of parking functions called parking garage functions. Parking functions have been well studied, but the concept of parking garage functions is new and introduced in the project. Parking garage functions are sequences that represent the parking garage level preferences of cars which lead to all cars parking on a level after a systematic placement. We found a recursive formula for the number of sequences that are a parking garage function. We also found a closed formula for a subset of …

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 …