Discrete Mathematics and Combinatorics Commons^™

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 …

Extremal Problems In Graph Saturation And Covering, Adam Volk

Department of Mathematics: Dissertations, Theses, and Student Research

This dissertation considers several problems in extremal graph theory with the aim of finding the maximum or minimum number of certain subgraph counts given local conditions. The local conditions of interest to us are saturation and covering. Given graphs F and H, a graph G is said to be F-saturated if it does not contain any copy of F, but the addition of any missing edge in G creates at least one copy of F. We say that G is H-covered if every vertex of G is contained in at least one copy of H. In the former setting, we …

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

How To Guard An Art Gallery: A Simple Mathematical Problem, Natalie Petruzelli

The Review: A Journal of Undergraduate Student Research

The art gallery problem is a geometry question that seeks to find the minimum number of guards necessary to guard an art gallery based on the qualities of the museum’s shape, specifically the number of walls. Solved by Václav Chvátal in 1975, the resulting Art Gallery Theorem dictates that ⌊n/3⌋ guards are always sufficient and sometimes necessary to guard an art gallery with n walls. This theorem, along with the argument that proves it, are accessible and interesting results even to one with little to no mathematical knowledge, introducing readers to common concepts in both geometry and graph …

A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar

Rose-Hulman Undergraduate Mathematics Journal

The Hadamard product (denoted by∗) of two power series A(x) =a₀+a₁x+a₂x²+···and B(x) =b₀+b₁x+b₂x²+··· is the power series A(x)∗B(x) =a₀b₀+a₁b₁x+a₂b₂x²+···. Although it is well known that the Hadamard product of two rational functions is also rational, a closed form expression of the Hadamard product of rational functions has not been found. Since any rational power series can be expanded by partial fractions as a polynomial plus a sum of power series …

Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang

Communications on Number Theory and Combinatorial Theory

Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be …

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 …

A Study Of Nash Equilibrium In Discrete Cases, Hallye Leleux

Mathematics Senior Capstone Papers

In game theory, Nash Equilibrium refers to a set of strategies in a non-cooperative game such that no player can benefit from changing their strategy. This paper examines the payoff matrices of the notable discrete games Battle of the Sexes, Matching Pennies, and The Prisoner’s Dilemma. We then create a custom discrete two player case and determine the pure and mixed strategy Nash Equilibria. After calculating the probabilities for each mixed strategy, we then determine the resulting payoff for each player and show how deviating from that strategy results in a lower payoff.

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 …

Prime Labelings On Planar Grid Graphs, Stephen James Curran

Theory & Applications of Graphs

It is known that for any prime p and any integer n such that 1≤n≤p there exists a prime labeling on the pxn planar grid graph P_pxP_n. We show that P_pxP_n has a prime labeling for any odd prime p and any integer n such that that p<n≤p².

Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan

Theory & Applications of Graphs

The betweenness centrality of an edge e is, summed over all u,v ∈ V(G), the ratio of the number of shortest u,v-paths in G containing e to the number of shortest u,v-paths in G. Graphs whose vertices all have the same edge betweenness centrality are called edge betweeness-uniform. It was recently shown by Madaras, Hurajová, Newman, Miranda, Fl´orez , and Narayan that of the over 11.7 million graphs with ten vertices or fewer, only four graphs are edge betweenness-uniform but not edge-transitive. In this paper we present new results involving properties of betweenness-uniform graphs.

Chromatic Polynomials Of Signed Book Graphs, Deepak Sehrawat, Bikash Bhattacharjya

Theory & Applications of Graphs

For m ≥ 3 and n ≥ 1, the m-cycle book graph B(m,n) consists of n copies of the cycle C_m with one common edge. In this paper, we prove that (a) the number of switching non-isomorphic signed B(m,n) is n+1, and (b) the chromatic number of a signed B(m,n) is either 2 or 3. We also obtain explicit formulas for the chromatic polynomials and the zero-free chromatic polynomials of switching non-isomorphic signed book graphs.

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 …

Connectedness Of Unit Distance Subgraphs Induced By Closed Convex Sets, Remie Janssen, Leonie Van Steijn

Theory & Applications of Graphs

The unit distance graph G¹_R^d is the infinite graph whose nodes are points in R^d, with an edge between two points if the Euclidean distance between these points is 1. The 2-dimensional version G¹_R2 of this graph is typically studied for its chromatic number, as in the Hadwiger-Nelson problem. However, other properties of unit distance graphs are rarely studied. Here, we consider the restriction of G¹_Rd to closed convex subsets X of R^d. We show that the graph G¹_Rd[X] is connected precisely when the radius of …

Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings, Richard M. Low, Dan Roberts

Theory & Applications of Graphs

Let A be a nontrivial abelian group and A* = A \ {0}. A graph is A-magic if there exists an edge labeling f using elements of A* which induces a constant vertex labeling of the graph. Such a labeling f is called an A-magic labeling and the constant value of the induced vertex labeling is called an A-magic value. In this paper, we use the Combinatorial Nullstellensatz to show the existence of Ζ_p-magic labelings (prime p ≥ 3 ) for various graphs, without having to construct the Ζ_p-magic labelings. Through many …

Facial Achromatic Number Of Triangulations With Given Guarding Number, Naoki Matsumoto, Yumiko Ohno

Theory & Applications of Graphs

A (not necessarily proper) k-coloring c : V(G) → {1,2,…k} of a graph G on a surface is a facial t-complete k-coloring if every t-tuple of colors appears on the boundary of some face of G. The maximum number k such that G has a facial t-complete k-coloring is called a facial t-achromatic number of G, denoted by ψ_t(G). In this paper, we investigate the relation between the facial 3-achromatic number and guarding number of triangulations on a surface, where a guarding number of a graph G embedded on a surface, …

New Formulations Of The Union-Closed Sets Conjecture, Sudipta Mallik

Mathematics Faculty Research

The union-closed sets conjecture states that if a finite set A of finite sets is union-closed and A ≠ {∅}, then there exists an element in ∪ _{A ∈ A} A that belongs to at least half of the sets in A. We present three new formulations of the union-closed conjecture in terms of matrices, graphs, and hypergraphs.

Positivity Among P-Partition Generating Functions, Nathan R. T. Lesnevich, Peter R. W. Mcnamara

Faculty Journal Articles

We seek simple conditions on a pair of labeled posets that determine when the difference of their (P,ω)-partition enumerators is F-positive, i.e., positive in Gessel's fundamental basis. This is a quasisymmetric analogue of the extensively studied problem of finding conditions on a pair of skew shapes that determine when the difference of their skew Schur functions is Schur-positive. We determine necessary conditions and separate sufficient conditions for F-positivity, and show that a broad operation for combining posets preserves positivity properties. We conclude with classes of posets for which we have conditions that are both necessary and …