Discrete Mathematics and Combinatorics Commons^™

Irreducible Representations From Group Actions On Trees, Charlie Liou

Master's Theses

We study the representations of the symmetric group $S_n$ found by acting on

labeled graphs and trees with $n$ vertices. Our main results provide

combinatorial interpretations that give the number of times the irreducible

representations associated with the integer partitions $(n)$ and $(1^n)$ appear

in the representations. We describe a new sign

reversing involution with fixed points that provide a combinatorial

interpretation for the number of times the irreducible associated with the

integer partition $(n-1, 1)$ appears in the representations.

Combinatorial Algorithms For Graph Discovery And Experimental Design, Raghavendra K. Addanki

Doctoral Dissertations

In this thesis, we study the design and analysis of algorithms for discovering the structure and properties of an unknown graph, with applications in two different domains: causal inference and sublinear graph algorithms. In both these domains, graph discovery is possible using restricted forms of experiments, and our objective is to design low-cost experiments. First, we describe efficient experimental approaches to the causal discovery problem, which in its simplest form, asks us to identify the causal relations (edges of the unknown graph) between variables (vertices of the unknown graph) of a given system. For causal discovery, we study algorithms …

Asymptotic Classes, Pseudofinite Cardinality And Dimension, Alexander Van Abel

Dissertations, Theses, and Capstone Projects

We explore the consequences of various model-theoretic tameness conditions upon the behavior of pseudofinite cardinality and dimension. We show that for pseudofinite theories which are either Morley Rank 1 or uncountably categorical, pseudofinite cardinality in ultraproducts satisfying such theories is highly well-behaved. On the other hand, it has been shown that pseudofinite dimension is not necessarily well-behaved in all ultraproducts of theories which are simple or supersimple; we extend such an observation by constructing simple and supersimple theories in which pseudofinite dimension is necessarily ill-behaved in all such ultraproducts. Additionally, we have novel results connecting various forms of asymptotic classes …

The On-Line Width Of Various Classes Of Posets., Israel R. Curbelo

Electronic Theses and Dissertations

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemer\'edi proved that any on-line algorithm could be forced to use $\binom{w+1}{2}$ chains to partition a poset of width $w$. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In the survey paper by Bosek et al., variants of the problem were studied where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size $d$. We prove …

Minimal Differential Graded Algebra Resolutions Related To Certain Stanley-Reisner Rings, Todd Anthony Morra

All Dissertations

We investigate algebra structures on resolutions of a special class of Cohen-Macaulay simplicial complexes. Given a simplicial complex, we define a pure simplicial complex called the purification. These complexes arise as a generalization of certain independence complexes and the resultant Stanley-Reisner rings have numerous desirable properties, e.g., they are Cohen-Macaulay. By realizing the purification in the context of work of D'alì, et al., we obtain a multi-graded, minimal free resolution of the Alexander dual ideal of the Stanley-Reisner ideal. We augment this in a standard way to obtain a resolution of the quotient ring, which is likewise minimal and multi-graded. …

Characteristic Sets Of Matroids, Dony Varghese

Doctoral Dissertations

Matroids are combinatorial structures that generalize the properties of linear independence. But not all matroids have linear representations. Furthermore, the existence of linear representations depends on the characteristic of the fields, and the linear characteristic set is the set of characteristics of fields over which a matroid has a linear representation. The algebraic independence in a field extension also defines a matroid, and also depends on the characteristic of the fields. The algebraic characteristic set is defined in the similar way as the linear characteristic set.

The linear representations and characteristic sets are well studied. But the algebraic representations and …

Verifying Sudoku Puzzles, Chelsea Schweer

Electronic Theses, Projects, and Dissertations

Sudoku puzzles, created by Meki Kaji around 1983, consist of a square 9 by 9 grid made up of 9 rows, 9 columns, and nine 3 by 3 square sub-grids called blocks. The goal of the puzzle is to be able to place the numbers 1 through 9 in every row, column, and block where no number is repeated in each row, column, and block. Imagine being given a completed Sudoku puzzle and having to check that it was solved correctly. You could just check all the rows columns and blocks (27 items), but is there a smaller number of …

Extensions And Bijections Of Skew-Shaped Tableaux And Factorizations Of Singer Cycles, Ga Yee Park

Doctoral Dissertations

This dissertation is in the field of Algebraic and Enumerative Combinatorics. In the first part of the thesis, we study the generalization of Naruse hook-length formula to mobile posets. Families of posets like Young diagrams of straight shapes and d-complete posets have hook-length product formulas to count linear extensions, whereas families like Young diagrams of skew shapes have determinant or positive sum formulas like the Naruse hook-length formula (NHLF). In 2020, Garver et. al. gave determinant formulas to count linear extensions of a family of posets called mobile posets that refine d-complete posets and border strip skew shapes. We give …

Studying Extended Sets From Young Tableaux, Eric S. Nofziger

Undergraduate Honors Thesis Collection

Young tableaux are combinatorial objects related to the partitions of an integer that have various applications in representation theory. These tableaux are defined as a left-justified set of n boxes filled with the numbers 1 through n and organized in rows, with the length of each row corresponding to a summand in the partition. In recent work of Graham–Precup–Russell, an association has been made between a given row-strict tableau and three disjoint subsets I, J, and K, also called extended sets. In this project, we begin to classify which extended sets correlate to a valid row-strict or standard tableau. We …

Quantum Dimension Polynomials: A Networked-Numbers Game Approach, Nicholas Gaubatz

Honors College Theses

The Networked-Numbers Game--a mathematical "game'' played on a simple graph--is incredibly accessible and yet surprisingly rich in content. The Game is known to contain deep connections to the finite-dimensional simple Lie algebras over the complex numbers. On the other hand, Quantum Dimension Polynomials (QDPs)--enumerative expressions traditionally understood through root systems--corresponding to the above Lie algebras are complicated to derive and often inaccessible to undergraduates. In this thesis, the Networked-Numbers Game is defined and some known properties are presented. Next, the significance of the QDPs as a method to count combinatorially interesting structures is relayed. Ultimately, a novel closed-form expression of …

Diederich-Fornæss Index On Boundaries Containing Crescents, Jason Demoulpied

Graduate Theses and Dissertations

The worm domain developed by Diederich and Fornæss is a classic example of a boundedpseudoconvex domains that fails to satisfy global regularity of the Bergman Projection, due to the set of weakly pseudoconvex points that form an annulus in its boundary. We instead examine a bounded pseudoconvex domain Ω ⊂ C2 whose set of weakly pseudoconvex points form a crescent in its boundary. In 2019, Harrington had shown that these types of domains satisfy global regularity of the Bergman Projection based on the existence of good vector fields. In this thesis we study the Regularized Diederich-Fornæss index of these domains, …

3-Uniform 4-Path Decompositions Of Complete 3-Uniform Hypergraphs, Rachel Mccann

Mathematical Sciences Undergraduate Honors Theses

The complete 3-uniform hypergraph of order v is denoted as K_v and consists of vertex set V with size v and edge set E, containing all 3-element subsets of V. We consider a 3-uniform hypergraph P₇, a path with vertex set {v₁, v₂, v₃, v₄, v₅, v₆, v₇} and edge set {{v₁, v₂, v₃}, {v₂, v₃, v₄}, {v₄, v₅, v₆}, {v₅, v_{6 …}

Enumerating Switching Isomorphism Classes Of Signed Graphs, Nathaniel Healy

Undergraduate Honors Theses

Let Γ be a simple connected graph, and let {+,−}^E(Γ) be the set of signatures of Γ. For σ a signature of Γ, we call the pair Σ = (Γ,σ) a signed graph of Γ. We may define switching functions ζ_X ∈ {+, −}^V (Γ) that negate the sign of every edge {u, v} incident with exactly one vertex in the fiber X = ζ^{−1}(−). The group Sw(Γ) of switching functions acts X on the set of signed graphs of Γ and induces an equivalence relation of switching classes in its orbits; there are 2^{|E(Γ)|−|V (Γ)|+1} such classes. More interestingly, …

Modern Theory Of Copositive Matrices, Yuqiao Li

Undergraduate Honors Theses

Copositivity is a generalization of positive semidefiniteness. It has applications in theoretical economics, operations research, and statistics. An $n$-by-$n$ real, symmetric matrix $A$ is copositive (CoP) if $x^T Ax \ge 0$ for any nonnegative vector $x \ge 0.$ The set of all CoP matrices forms a convex cone. A CoP matrix is ordinary if it can be written as the sum of a positive semidefinite (PSD) matrix and a symmetric nonnegative (sN) matrix. When $n < 5,$ all CoP matrices are ordinary. However, recognizing whether a given CoP matrix is ordinary and determining an ordinary decomposition (PSD + sN) is still an unsolved problem. Here, we give an overview on modern theory of CoP matrices, talk about our progress on the ordinary recognition and decomposition problem, and emphasis the graph theory aspect of ordinary CoP matrices.

An Implementation Of Integrated Information Theory In Resting-State Fmri, Idan E. Nemirovsky

Electronic Thesis and Dissertation Repository

Integrated Information Theory (IIT) is a framework developed to explain consciousness, arguing that conscious systems consist of interacting elements that are integrated through their causal properties. In this study, we present the first application of IIT to functional magnetic resonance imaging (fMRI) data and investigate whether its principal metric, Phi, can meaningfully quantify resting-state cortical activity patterns. Data was acquired from 17 healthy subjects who underwent sedation with propofol, a short acting anesthetic. Using PyPhi, a software package developed for IIT, we thoroughly analyze how Phi varies across different networks and throughout sedation. Our findings indicate that variations in Phi …

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 …

Unavoidable Structures In Large And Infinite Graphs, Sarah Allred

LSU Doctoral Dissertations

In this work, we present results on the unavoidable structures in large connected and large 2-connected graphs. For the relation of induced subgraphs, Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either K_r or K_r. It is well known that, for every positive integer r, every sufficiently large connected graph contains an induced subgraph isomorphic to one of K_r, K_1,r, and P_r. We prove an analogous result for 2-connected graphs. Similarly, for infinite graphs, every infinite connected graph contains an induced subgraph …

The Enumeration Of Minimum Path Covers Of Trees, Merielyn Sher

Undergraduate Honors Theses

A path cover of a tree T is a collection of induced paths of T that are vertex disjoint and cover all the vertices of T. A minimum path cover (MPC) of T is a path cover with the minimum possible number of paths, and that minimum number is called the path cover number of T. A tree can have just one or several MPC's. Prior results have established equality between the path cover number of a tree T and the largest possible multiplicity of an eigenvalue that can occur in a symmetric matrix whose graph is that tree. We …

Moving Polygon Methods For Incompressible Fluid Dynamics, Chris Chartrand

Doctoral Dissertations

Hybrid particle-mesh numerical approaches are proposed to solve incompressible fluid flows. The methods discussed in this work consist of a collection of particles each wrapped in their own polygon mesh cell, which then move through the domain as the flow evolves. Variables such as pressure, velocity, mass, and momentum are located either on the mesh or on the particles themselves, depending on the specific algorithm described, and each will be shown to have its own advantages and disadvantages. This work explores what is required to obtain local conservation of mass, momentum, and convergence for the velocity and pressure in a …

Minimality Of Integer Bar Visibility Graphs, Emily Dehoff

University Honors Theses

A visibility representation is an association between the set of vertices in a graph and a set of objects in the plane such that two objects have an unobstructed, positive-width line of sight between them if and only if their two associated vertices are adjacent. In this paper, we focus on integer bar visibility graphs (IBVGs), which use horizontal line segments with integer endpoints to represent the vertices of a given graph. We present results on the exact widths of IBVGs of paths, cycles, and stars, and lower bounds on trees and general graphs. In our main results, we find …

Finding Triangular Cayley Maps With Graph Touring, Hannah Hendrickson

Honors Program Theses

We develop a method for determining whether certain kinds of Cayley maps can exist by using multi-digraph representations of the data in the Cayley maps. Euler tours of these multi-digraphs correspond exactly to the permutations which define Cayley maps. We also begin to classify which 3-regular multi-digraphs have "non-backtracking" Euler tours in general.

Counting The Moduli Space Of Pentagons On Finite Projective Planes, Maxwell Hosler

Senior Independent Study Theses

Finite projective planes are finite incidence structures which generalize the concept of the real projective plane. In this paper, we consider structures of points embedded in these planes. In particular, we investigate pentagons in general position, meaning no three vertices are colinear. We are interested in properties of these pentagons that are preserved by collineation of the plane, and so can be conceived as properties of the equivalence class of polygons up to collineation as a whole. Amongst these are the symmetries of a pentagon and the periodicity of the pentagon under the pentagram map, and a generalization of …

On The Polytopal Generalization Of Sperner’S Lemma, Amit Harlev

HMC Senior Theses

We introduce and prove Sperner’s lemma, the well known combinatorial analogue of the Brouwer fixed point theorem, and then attempt to gain a better understanding of the polytopal generalization of Sperner’s lemma conjectured in Atanassov (1996) and proven in De Loera et al. (2002). After explaining the polytopal generalization and providing examples, we present a new, simpler proof of a slightly weaker result that helps us better understand the result and why it is correct. Some ideas for how to generalize this proof to the complete result are discussed. In the last two chapters we provide a brief introduction to …

Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi

HMC Senior Theses

In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in 𝐏 are thought of as 0-turn games, 𝐍𝐏 as 1-turn “puzzle” games, and in general 𝚺ₖ𝐏 as 𝑘-turn games, in which decision problems answer the binary question, “can the starting player guarantee a win?” We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of 𝑘-turn CIRCUIT SATISFIABILITY games, whose 𝚺ₖ𝐏-completeness is assumed from prior work (we briefly justify this assumption …

Stroke Clustering And Fitting In Vector Art, Khandokar Shakib

Senior Independent Study Theses

Vectorization of art involves turning free-hand drawings into vector graphics that can be further scaled and manipulated. In this paper, we explore the concept of vectorization of line drawings and study multiple approaches that attempt to achieve this in the most accurate way possible. We utilize a software called StrokeStrip to discuss the different mathematics behind the parameterization and fitting involved in the drawings.

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 …

Automated Conjecturing On The Independence Number And Minimum Degree Of Diameter-2-Critical Graphs, Joshua R. Forkin

Theses and Dissertations

A diameter-2-critical (D2C) graph is a graph with diameter two such that removing any edge increases the diameter or disconnects the graph. In this paper, we look at other lesser-studied properties of D2C graphs, focusing mainly on their independence number and minimum degree. We show that there exist D2C graphs with minimum degree strictly larger than their independence number, and that this gap can be arbitrarily large. We also exhibit D2C graphs with maximum number of common neighbors strictly greater than their independence number, and that this gap can be arbitrarily large. Furthermore, we exhibit a D2C graph whose number …

Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer

Theses and Dissertations--Computer Science

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a …

On Generalizations Of Supereulerian Graphs, Sulin Song

Graduate Theses, Dissertations, and Problem Reports

A graph is supereulerian if it has a spanning closed trail. Pulleyblank in 1979 showed that determining whether a graph is supereulerian, even when restricted to planar graphs, is NP-complete. Let $\kappa'(G)$ and $\delta(G)$ be the edge-connectivity and the minimum degree of a graph $G$, respectively. For integers $s \ge 0$ and $t \ge 0$, a graph $G$ is $(s,t)$-supereulerian if for any disjoint edge sets $X, Y \subseteq E(G)$ with $|X|\le s$ and $|Y|\le t$, $G$ has a spanning closed trail that contains $X$ and avoids $Y$. This dissertation is devoted to providing some results on $(s,t)$-supereulerian graphs and …

Polychromatic Colorings Of Certain Subgraphs Of Complete Graphs And Maximum Densities Of Substructures Of A Hypercube, Ryan Tyler Hansen

Graduate Theses, Dissertations, and Problem Reports

If G is a graph and H is a set of subgraphs of G, an edge-coloring of G is H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, poly_HG, is the largest number of colors in an H-polychromatic coloring. We determine poly_HG exactly when G is a complete graph on n vertices, q a fixed nonnegative integer, and H is the family of one of: all matchings spanning n-q vertices, all 2-regular graphs spanning at least n-q vertices, or all cycles of length precisely n-q. …