Unavoidable Structures In Large And Infinite Graphs,
2022
Louisiana State University and Agricultural and Mechanical College
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 Kr or Kr. It is well known that, for every positive integer r, every sufficiently large connected graph contains an induced subgraph isomorphic to one of Kr, K1,r, and Pr. 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,
2022
Louisiana Tech University
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.
Prime Labelings On Planar Grid Graphs,
2022
University of Pittsburgh - Johnstown
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 PpxPn. We show that PpxPn has a prime labeling for any odd prime p and any integer n such that that p<n≤p2.
Characterizing Edge Betweenness-Uniform Graphs,
2022
University of Economics, Tajovského
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,
2022
Indian Institute of Technology Guwahati
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 Cm 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,
2022
Portland State University
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,
2022
Delft University of Technology
Connectedness Of Unit Distance Subgraphs Induced By Closed Convex Sets, Remie Janssen, Leonie Van Steijn
Theory & Applications of Graphs
The unit distance graph G1Rd is the infinite graph whose nodes are points in Rd, with an edge between two points if the Euclidean distance between these points is 1. The 2-dimensional version G1R2 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 G1Rd to closed convex subsets X of Rd. We show that the graph G1Rd[X] is connected precisely when the radius of …
Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings,
2022
San Jose State University
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,
2022
Keio University
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,
2022
Marshall University
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,
2022
Washington University in St. Louis
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 …
Generating B-Nomial Numbers,
2022
Shippensburg University of Pennsylvania
Generating B-Nomial Numbers, Ji Young Choi
Communications on Number Theory and Combinatorial Theory
This paper presents three new ways to generate each type of b-nomial numbers: We develop ordinary generating functions, we find a whole new set of recurrence relations, and we identify each b-nomial number as a single binomial coefficient or as an alternating sum of products of two binomial coefficients.
On The Polytopal Generalization Of Sperner’S Lemma,
2022
Claremont Colleges
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,
2022
Claremont Colleges
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 …
Finding Triangular Cayley Maps With Graph Touring,
2022
Rollins College
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.
Automated Conjecturing On The Independence Number And Minimum Degree Of Diameter-2-Critical Graphs,
2022
Virginia Commonwealth University
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 …
Combinatorial Optimization With Photonics-Inspired Clock Models,
2022
CUNY Queens College
Combinatorial Optimization With Photonics-Inspired Clock Models, Mostafa Honari-Latifpour, Matthew S. Mills, Mohammad-Ali Miri
Publications and Research
NP-hard combinatorial optimization problems are in general hard problems that their computational complexity grows faster than polynomial scaling with the size of the problem. Thus, over the years there has been a great interest in developing unconventional methods and algorithms for solving such problems. Here, inspired by the nonlinear optical process of q-photon down-conversion, in which a photon is converted into q degenerate lower energy photons, we introduce a nonlinear dynamical model that builds on coupled single-variable phase oscillators and allows for efficiently approximating the ground state of the classical q-state planar Potts Hamiltonian. This reduces the exhaustive search in …
Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums,
2022
University of Montana
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 …
Multicolor Ramsey And List Ramsey Numbers For Double Stars,
2022
University of Central Florida
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 Kn 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 …
On Flow Polytopes, Nu-Associahedra, And The Subdivision Algebra,
2022
University of Kentucky
On Flow Polytopes, Nu-Associahedra, And The Subdivision Algebra, Matias Von Bell
Theses and Dissertations--Mathematics
This dissertation studies the geometry and combinatorics related to a flow polytope Fcar(ν) constructed from a lattice path ν, whose volume is given by the ν-Catalan numbers. It begins with a study of the ν-associahedron introduced by Ceballos, Padrol, and Sarmiento in 2019, but from the perspective of Schröder combinatorics. Some classical results for Schröder paths are extended to the ν-setting, and insights into the geometry of the ν-associahedron are obtained by describing its face poset with two ν-Schröder objects. The ν-associahedron is then shown to be dual to a framed triangulation of Fcar(ν), which is a …
