Discrete Mathematics Seminar
Spring 2022
March 25  M. Barrus, URI  Cliques in the realization graph of a degree sequence 
Abstract:
Given a degree sequence $d$ of a finite graph, there are usually many different realizations of the sequence by labeled graphs. The realization graph of $d$ is the graph whose vertices are these realizations, where edges join vertices corresponding to realizations that can be changed into each other via single editing operation on an edge set. The realization graph is known to be connected for all $d$, and it is conjectured that it always has a Hamilton path or cycle. After a quick introduction to the realization graph, we present a necessary and sufficient condition for cliques of any fixed size to appear in the realization graph. We also determine the degree sequences $d$ whose realization graph is the complete graph $K_n$ for all $n$. This is joint work with Nathan Haronian (Brown University).

Fall 2021
October 29  B. Kinnersley, URI  The Localization Game on Graphs 
Abstract:
In the localization game, a team of cops attempts to locate a robber on a graph G. Initially, the robber positions himself at some vertex of G. Next, each cop probes a vertex of G, and the cops learn the distance from each probe to the robber's location. If the cops can pinpoint the robber's location, then the cops win; otherwise, the robber can run to a neighboring vertex. The game continues, alternating between cop probes and robber moves, until the cops win (or concede). The localization number of G is the minimum number of cops  that is, the minimum number of probes per turn  needed for the cops to win. In this talk, we present some recent work on the localization number, including bounds on the localization numbers of outerplanar graphs and hypercubes, along with a surprising connection to the chromatic number. This is joint work with Anthony Bonato.


October 22  N. Townsend, URI  Catching an InfiniteSpeed Robber on Grids 
Abstract:
Recently, there has been considerable interest in variants of Cops and Rob
bers in which the robber is more mobile than the cops. We focus on the infinite
speed robber variant of the game, wherein the robber may traverse an arbitrarily
long copfree path on their turn. In this talk, we determine the infinitespeed
cop number on twodimensional Cartesian gridlike graphs up to a small ad
ditive constant, and we give asymptotic bounds for several families of higher
dimensional Cartesian grids. This is joint work with Dr. Kinnersley.


October 15  M. Barrus, URI  The Erd\H{o}sGallai differences of a degree sequence 
Abstract:
The Erd\H{o}sGallai criteria are a set of inequalities that characterize lists of nonnegative integers that
are degree sequences of finite simple graphs. A number of graph families, including the split, threshold, and
weakly threshold graphs, have degree sequence characterizations that rely on one or more of the Erd\H{o}sGallai
inequalities holding with equality or near equality.
We define an Erd\H{o}sGallai difference to be the difference of the two sides in one of the Erd\H{o}sGallai inequalities.
After surveying known appearances of the Erd\H{o}sGallai differences, we look at the behavior of these differences under
graph complementation and in the context of two partial orders. In particular, we show that the maximum and last ``principal''
Erd\H{o}sGallai difference are shared by the degree sequences of a graph and of its complement, and they are monotone
in the induced subgraph poset and in a poset introduced by S.B. Rao. As consequences, we give broader context to a few
properties of split and threshold graphs. We conclude with a few directions for further study.
