Discrete Mathematics Group at URI

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.

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).

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.