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 Infinite-Speed 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 cop-free path on their turn. In this talk, we determine the infinite-speed cop number on two-dimensional Cartesian grid-like 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}s-Gallai differences of a degree sequence
Abstract:    The Erd\H{o}s-Gallai 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}s-Gallai inequalities holding with equality or near equality. We define an Erd\H{o}s-Gallai difference to be the difference of the two sides in one of the Erd\H{o}s-Gallai inequalities. After surveying known appearances of the Erd\H{o}s-Gallai 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}s-Gallai 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.

Past semesters:

           2021-2022               2020-2021               2019-2020               2018-2019   
           2017-2018               2016-2017               2015-2016               2014-2015   
           2013-2014               2012-2013               2011-2012               2010-2011   
           2009-2010               2008-2009               2007-2008               2006-2007   
           2005-2006               2004-2005               2003-2004               2002-2003   

Journals in Discrete Mathematics and related fields