Discrete Mathematics and Combinatorics Commons^™

Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. Interestingly, there are many extensions of this theorem to multiple dimensions ...

A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

Theory and Applications of Graphs

Given a graph $H$ and a positive integer $k$, the $k$-color Gallai-Ramsey number $gr_{k}(K_{3} : H)$ is defined to be the minimum number of vertices $n$ for which any $k$-coloring of the complete graph $K_{n}$ contains either a rainbow triangle or a monochromatic copy of $H$. The behavior of these numbers is rather well understood when $H$ is bipartite but when $H$ is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs $H$ to a value that we conjecture to be sharp ...

Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

Theory and Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of ...

Zero Forcing And Power Domination For Graph Products, Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben, Violeta Vasilevska, Brian Wissman

Mathematics Publications

The power domination number arose from the monitoring of electrical networks, and methods for its determination have the associated application. The zero forcing number arose in the study of maximum nullity among symmetric matrices described by a graph (and also in control of quantum systems and in graph search algorithms). There has been considerable effort devoted to the determination of the power domination number, the zero forcing number, and maximum nullity for specific families of graphs. In this paper we exploit the natural relationship between power domination and zero forcing to obtain results for the power domination number of tensor ...

The Relationship Between K-Forcing And K-Power Domination, Daniela Ferrero, Leslie Hogben, Franklin H.J. Kenter, Michael Young

Mathematics Publications

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of k-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, k-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of k-forcing and k-power domination, providing a new approach to analyze both ...

Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhart, Theodore Tranel

Mathematics Publications

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.

Polychromatic Colorings On The Hypercube, John Goldwasser, Bernard Lidicky, Ryan R. Martin, David Offner, John Talbot, Michael Young

Mathematics Publications

Given a subgraph G of the hypercube Qn, a coloring of the edges of Qn such that every embedding of G contains an edge of every color is called a G-polychromatic coloring. The maximum number of colors with which it is possible to G-polychromatically color the edges of any hypercube is called the polychromatic number of G. To determine polychromatic numbers, it is only necessary to consider a specific type of coloring, which we call simple. The main tool for finding upper bounds on polychromatic numbers is to translate the question of polychromatically coloring the hypercube so every embedding of ...

Fine Structure Of 4-Critical Triangle-Free Graphs Iii. General Surfaces, Zdenek Dvorak, Bernard Lidicky

Mathematics Publications

Dvořák, Král', and Thomas [Three-Coloring Triangle-Free Graphs on Surfaces IV. Bounding Face Sizes of 4-Critical Graphs, preprint, arXiv:1404.6356v3, 2015; Three-Coloring Triangle-Free Graphs on Surfaces VI. 3-Colorability of Quadrangulations, preprint, arXiv:1509.01013, 2015] gave a description of the structure of triangle-free graphs on surfaces with respect to 3-coloring. Their description, however, contains two substructures (both related to graphs embedded in a plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.

On The Strong Chromatic Index Of Sparse Graphs, Philip Deorsey, Michael Ferrara, Nathan Graber, Stephen G. Hartke, Luke L. Nelsen, Eric Sullivan, Sogol Jahanbekam, Bernard Lidicky, Derrick Stolee, Jennifer White

Mathematics Publications

The strong chromatic index of a graph G, denoted χ′s(G), is the least number of colors needed to edge-color G so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted χ′s,ℓ(G), is the least integer k such that if arbitrary lists of size k are assigned to each edge then G can be edge-colored from those lists where edges at distance at most two receive distinct colors.

We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if G is a subcubic planar graph with ...

Pbw Bases And Marginally Large Tableaux In Type D, Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

We give an explicit description of the unique crystal isomorphism between two realizations of B(∞) in type D: that using marginally large tableaux and that using PBW monomials with respect to one particularly nice reduced expression of the longest word

A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu

Theory and Applications of Graphs

The concept of monochromatic connection of graphs was introduced by Caro and Yuster in 2011. Recently, a lot of results have been published about it.
In this survey, we attempt to bring together all the results that dealt with it.
We begin with an introduction, and then classify the results into the following categories: monochromatic connection coloring of edge-version, monochromatic connection coloring of vertex-version, monochromatic index, monochromatic connection coloring of total-version.

Hilbert Bases, Descent Statistics, And Combinatorial Semigroup Algebras, Mccabe J. Olsen

Theses and Dissertations--Mathematics

The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials.

Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory.

In Chapter ...

Polytopes Associated To Graph Laplacians, Marie Meyer

Theses and Dissertations--Mathematics

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, P_G, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, P_D.

Basic properties of both families of simplices, P_G and P_D, are established using techniques ...

Sparse Trees With A Given Degree Sequence, Ao Shen

Electronic Theses and Dissertations

In this thesis, we consider the properties of sparse trees and summarized a certain class of trees under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph theory. Steiner k􀀀 Wiener index can be regarded as the generalization of Wiener index, when k = 2, Steiner Wiener index is the same as Wiener index. Steiner k􀀀 Wiener index of a tree T is the ...

Notes On The Proof Of The Van Der Waerden Permanent Conjecture, Vicente Valle Martinez

Creative Components

The permanent of an $n\times n$ matrix $A=(a_{i j})$ with real entries is defined by the sum $$\sum_{\sigma \in S_n} \prod_{i=1}^{n} a_{i \sigma(i)}$$ where $S_n$ denotes the symmetric group on the $n$-element set $\{1,2,\dots,n\}$. In this creative component we survey some known properties of permanents, calculation of permanents for particular types of matrices and their applications in combinatorics and linear algebra. Then we follow the lines of van Lint's exposition of Egorychev's proof for the van der Waerden's conjecture on the permanents of doubly ...

An Incidence Approach To The Distinct Distances Problem, Bryce Mclaughlin

HMC Senior Theses

In 1946, Erdös posed the distinct distances problem, which asks for the minimum number of distinct distances that any set of n points in the real plane must realize. Erdös showed that any point set must realize at least &Omega(n^1/2) distances, but could only provide a construction which offered &Omega(n/&radic(log(n)))$ distances. He conjectured that the actual minimum number of distances was &Omega(n^1-&epsilon) for any &epsilon > 0, but that sublinear constructions were possible. This lower bound has been improved over the years, but Erdös' conjecture seemed to hold until in 2010 ...

Self-Assembly Of Dna Graphs And Postman Tours, Katie Bakewell

UNF Graduate Theses and Dissertations

DNA graph structures can self-assemble from branched junction molecules to yield solutions to computational problems. Self-assembly of graphs have previously been shown to give polynomial time solutions to hard computational problems such as 3-SAT and k-colorability problems. Jonoska et al. have proposed studying self-assembly of graphs topologically, considering the boundary components of their thickened graphs, which allows for reading the solutions to computational problems through reporter strands. We discuss weighting algorithms and consider applications of self-assembly of graphs and the boundary components of their thickened graphs to problems involving minimal weight Eulerian walks such as the Chinese Postman Problem and ...

Finding Planted Cliques In Erdős–Rényi Random Graphs: Improving Previous Methods And Expanding Applications, Megan Sochinski

Undergraduate Honors Theses

In this paper, we will discuss new methods for finding planted cliques within Erdős–Rényi random graphs. An Erdős–Rényi random graph is a graph with n vertices, where each vertex is connected to each other vertex with some probability p, independent of all other choices. The planted clique problem asks us to find the most efficient way to find a planted clique in an Erdős–Rényi random graph. A planted clique is a secretly chosen set of vertices in the graph that are purposefully connected with edges added to the graph until all of the selected vertices are connected ...

Uses Of Mathematics In Computer Animation And 3d Rendering Software, Peter Rock

Undergraduate Honors Theses

As the title suggests, this paper discusses the applications of several mathematical concepts to computer animation software generally used in the creation of movies and video games. Topics covered will include differential forms, conformal maps, surface texturing, and lighting techniques. It is not the goal of this paper to present anything particularly novel to the mathematical community, but rather to present something that is entertaining to read that will hopefully engage both mathematicians and sane people alike. This paper has been carefully crafted so that it should be accessible to most people with a Calc. I background. That being said ...

On The Planarity Of Generalized Line Graphs, Khawlah H. Alhulwah, Mohra Zayed, Ping Zhang

Theory and Applications of Graphs

One of the most familiar derived graphs is the line graph. The line graph $L(G)$ of a graph $G$ is that graph whose vertices are the edges of $G$ where two vertices of $L(G)$ are adjacent if the corresponding edges are adjacent in~$G$. Two nontrivial paths $P$ and $Q$ in a graph $G$ are said to be adjacent paths in $G$ if $P$ and $Q$ have exactly one vertex in common and this vertex is an end-vertex of both $P$ and $Q$. For an integer $\ell \ge 2$, the $\ell$-line graph $L_{\ell}(G)$ of a ...