Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2018

April 27 E. Peterson, URI Burning Edges in Cops and Robbers Games

April 13 J. Smith, URI On mod-2 homology of random simplicial complexes

April 6 J. Chavez-Casillas, URI Models of complex networks: an introduction

March 30 B. Kinnersley, URI Martingales and Random Graphs
Abstract:    Martingales are a simple probabilistic tool with some sophisticated applications in graph theory (along with a variety of other disciplines). In this talk, we give a gentle introduction to martingales and demonstrate some ways in which they can be used to study the properties of random graphs. Only a very basic knowledge of probability will be assumed.

March 23 N. Townsend, URI Lazy Cops and Robbers on Graphs: Chess Graphs and Large Lazy Cop Number
Abstract:    In the game of Cops and Robbers on Graphs, a team of cops and a robber take turns moving on the vertex set of a graph. If a cop occupies the same vertex as the robber, then the cops win. If it can be shown that the robber can evade the cops indefinitely, then he wins. Primarily, we consider the variant of the game called Lazy Cops and Robbers, wherein only one cop is allowed to move per turn. We give bounds for the cop numbers and lazy cop numbers of Queens Graphs, and examine both games on Rooks Graphs. We also will discuss the properties of the n x n Rooks Graph in depth, as well as share progress toward proving that it is the unique smallest graph with lazy cop number n.

March 9 B. Lantz, URI Symmetries of Tetravalent Metacirculant Graphs of Type III
Abstract:    This talk will examine tetravelent metacirculant graphs of type III, specifically those that are possibly edge-transitive. The goal is to classify all possible tetravalent edge-transitive metacirculant graphs of type III. In doing so, LR structures, which possibly generate edge-transitive graphs, will be examined. Properties, restrictions, and isomorphisms of the parameters of type III graphs will be examined and eventually a few infinite families of LR structures will be introduced.

March 2 M. Barrus, URI On Erdos and extremal set theory
Abstract:    Paul Erdos is one of the first champions of using probabilistic methods to answer questions in discrete mathematics. In this talk we give probabilistic proofs due to Alon--Frankl and Katona of two Erdos-related results on families of sets. The first answers a question studied by Erdos and coauthor Daykin: If we have a set S and a family F of subsets from S, then what is the largest number of pairs (A,B) we can draw from F such that A and B are disjoint? The second question, answered by a famous result due to Erdos, Ko, and Rado, is this: If F is a family of subsets of {1,...,n} such that every pair of subsets from F have at least one element in common, then how many subsets can there be in F?

February 23 J. Chavez-Casillas, URI A survey on Point Processes and their Applications

February 16 L. Thoma, URI An introduction to random graphs

Fall 2017

December 8 N. Daniels, URI From biology to astronomy: the shape of big data

December 1 S. Gambino, URI Report on 'On-line list colouring of graphs' by X. Zhu

November 15 A. Bonato, Ryerson University Burning spiders and path forests
Abstract:    Graph burning is a simplified model for the spread of memes and contagion in social networks. A fire breaks out in each time-step and spreads to its neighbours. The burning number of a graph measures the number of time-steps it takes so that all vertices are burning. While it is conjectured that the burning number of a connected graph of order n is a most the ceiling of the square root of n, this remains open in general.
We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests. Host: Bill Kinnersley

November 10 J. Guillaume, URI The Distinguishing Number and Distinguishing Chromatic Number of a Graph
Abstract:    Let's say we have a ring of $n$ seemingly identical keys, which are assigned to different doors, and our goal is to be able to distinguish them using a variety of handle shapes. From the point of view of graph theory, this is finding out how many labels (colors) are needed to distinguish the vertices of $C_n$, so that the only label-preserving (color-preserving) automorphism of $C_n$ is the identity. Extending this idea to any graph $G$, we want, in other words, label the vertices in a way that destroys the symmetries of the graph. Let $r$ be the number of labels used to accomplish this goal; we thus say that $G$ has an $r$-distinguishing labeling and the distinguishing number of $G$, denoted $D(G)$, is the minimum $r$ such that $G$ has an $r$-distinguishing labeling. Furthermore, if we attain this objective using a proper labeling (coloring), then we call the minimum $r$, the distinguishing chromatic number of $G$. From this talk, the audience will learn about the history (which is very recent), known results (surprising to say the least), and open questions related to both concepts. Our independent study project on this topic and early results will also be discussed.

November 3 M. Barrus, URI Independence number and the Havel-Hakimi Residue
Abstract:    The Havel-Hakimi algorithm begins with the degree sequence of a graph and iteratively reduces it to a list of zeroes. The number of zeroes produced, known as the residue, is a lower bound on the independence number of the graph. We discuss the tightness of the bound from a few perspectives, first in the situation in which the degree sequence does not have many realizations, and second in the situation where the graph's structure allows a vertex deletion sequence that mimics the Havel-Hakimi process.

October 27 L. Thoma, URI Edge density, homomorphisms, and correlations: combinatorics and analysis

October 20 W. Kinnersley, URI Bounds on the length of a game of Cops and Robbers

April 27	E. Peterson, URI	Burning Edges in Cops and Robbers Games
April 13	J. Smith, URI	On mod-2 homology of random simplicial complexes
April 6	J. Chavez-Casillas, URI	Models of complex networks: an introduction
March 30	B. Kinnersley, URI	Martingales and Random Graphs
		Abstract: Martingales are a simple probabilistic tool with some sophisticated applications in graph theory (along with a variety of other disciplines). In this talk, we give a gentle introduction to martingales and demonstrate some ways in which they can be used to study the properties of random graphs. Only a very basic knowledge of probability will be assumed.
March 23	N. Townsend, URI	Lazy Cops and Robbers on Graphs: Chess Graphs and Large Lazy Cop Number
		Abstract: In the game of Cops and Robbers on Graphs, a team of cops and a robber take turns moving on the vertex set of a graph. If a cop occupies the same vertex as the robber, then the cops win. If it can be shown that the robber can evade the cops indefinitely, then he wins. Primarily, we consider the variant of the game called Lazy Cops and Robbers, wherein only one cop is allowed to move per turn. We give bounds for the cop numbers and lazy cop numbers of Queens Graphs, and examine both games on Rooks Graphs. We also will discuss the properties of the n x n Rooks Graph in depth, as well as share progress toward proving that it is the unique smallest graph with lazy cop number n.
March 9	B. Lantz, URI	Symmetries of Tetravalent Metacirculant Graphs of Type III
		Abstract: This talk will examine tetravelent metacirculant graphs of type III, specifically those that are possibly edge-transitive. The goal is to classify all possible tetravalent edge-transitive metacirculant graphs of type III. In doing so, LR structures, which possibly generate edge-transitive graphs, will be examined. Properties, restrictions, and isomorphisms of the parameters of type III graphs will be examined and eventually a few infinite families of LR structures will be introduced.
March 2	M. Barrus, URI	On Erdos and extremal set theory
		Abstract: Paul Erdos is one of the first champions of using probabilistic methods to answer questions in discrete mathematics. In this talk we give probabilistic proofs due to Alon--Frankl and Katona of two Erdos-related results on families of sets. The first answers a question studied by Erdos and coauthor Daykin: If we have a set S and a family F of subsets from S, then what is the largest number of pairs (A,B) we can draw from F such that A and B are disjoint? The second question, answered by a famous result due to Erdos, Ko, and Rado, is this: If F is a family of subsets of {1,...,n} such that every pair of subsets from F have at least one element in common, then how many subsets can there be in F?
February 23	J. Chavez-Casillas, URI	A survey on Point Processes and their Applications
February 16	L. Thoma, URI	An introduction to random graphs

December 8	N. Daniels, URI	From biology to astronomy: the shape of big data
December 1	S. Gambino, URI	Report on 'On-line list colouring of graphs' by X. Zhu
November 15	A. Bonato, Ryerson University	Burning spiders and path forests
		Abstract: Graph burning is a simplified model for the spread of memes and contagion in social networks. A fire breaks out in each time-step and spreads to its neighbours. The burning number of a graph measures the number of time-steps it takes so that all vertices are burning. While it is conjectured that the burning number of a connected graph of order n is a most the ceiling of the square root of n, this remains open in general. We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests. Host: Bill Kinnersley
November 10	J. Guillaume, URI	The Distinguishing Number and Distinguishing Chromatic Number of a Graph
		Abstract: Let's say we have a ring of $n$ seemingly identical keys, which are assigned to different doors, and our goal is to be able to distinguish them using a variety of handle shapes. From the point of view of graph theory, this is finding out how many labels (colors) are needed to distinguish the vertices of $C_n$, so that the only label-preserving (color-preserving) automorphism of $C_n$ is the identity. Extending this idea to any graph $G$, we want, in other words, label the vertices in a way that destroys the symmetries of the graph. Let $r$ be the number of labels used to accomplish this goal; we thus say that $G$ has an $r$-distinguishing labeling and the distinguishing number of $G$, denoted $D(G)$, is the minimum $r$ such that $G$ has an $r$-distinguishing labeling. Furthermore, if we attain this objective using a proper labeling (coloring), then we call the minimum $r$, the distinguishing chromatic number of $G$. From this talk, the audience will learn about the history (which is very recent), known results (surprising to say the least), and open questions related to both concepts. Our independent study project on this topic and early results will also be discussed.
November 3	M. Barrus, URI	Independence number and the Havel-Hakimi Residue
		Abstract: The Havel-Hakimi algorithm begins with the degree sequence of a graph and iteratively reduces it to a list of zeroes. The number of zeroes produced, known as the residue, is a lower bound on the independence number of the graph. We discuss the tightness of the bound from a few perspectives, first in the situation in which the degree sequence does not have many realizations, and second in the situation where the graph's structure allows a vertex deletion sequence that mimics the Havel-Hakimi process.
October 27	L. Thoma, URI	Edge density, homomorphisms, and correlations: combinatorics and analysis
October 20	W. Kinnersley, URI	Bounds on the length of a game of Cops and Robbers