Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2017

April 28 M. Williams, URI Report on 'Unavoidable Induced Subgraphs in Large Graphs with no Homogeneous Sets' by M. Chudnovsky, R. Kim, S. Oum, P. Seymour

April 7 J. Erickson, URI Waiter-Client and Client-Waiter Hamiltonicity Games on Random Graphs
Abstract:    The theory of positional games on graphs has developed into a highly studied area of combinatorics. In this talk, I'll explain the basics of two types of positional games played on graphs---the Waiter-Client and Client-Waiter games---and introduce the concepts of random graphs, expanders, and boosters. Then, I will use these topics to prove that when played on random graphs with the winning sets of the games being Hamiltonian cycles, we can derive sharp thresholds for players' winning strategies for these games. This is a report on 'Waiter-Client and Client-Waiter Hamiltonicity games on random graphs by D. Hefetz, M. Krivelevich, and W. Tan.

March 31 M. Kempton, CMSA, Harvard University Non-backtracking Random Walks and Polya's Recurrence Theorem
Abstract:    The theory of random walks on graphs has become a major area of study in graph theory. Random walks are the basis for many important algorithms involving graphs in the real world, and there theory has been widely studied and is largely well-understood. In recent years, the study of non-backtracking random walks has gained interest, although their analysis has proven challenging. I will give some background on non-backtracking random walks on graphs, and present a non-backtracking version of a classical theorem in the theory of random walks on graphs: Polya's recurrence theorem. Host: Michael Barrus.

March 24 M. Barrus, URI The Grone-Merris Conjecture
Abstract:    Spectral graph theory seeks to find relationships between the eigenvalues of a graph's adjacency matrix (or other related matrices) and the properties of the graph. In particular, in 1994 Grone and Merris conjectured a relationship between the degree sequence of an arbitrary graph $G$ and the eigenvalues of the Laplacian matrix of $G$. In this talk we introduce spectral graph theory, describe the relationship between degree sequences and eigenvalues, and present highlights of Hua Bai's 2011 proof of the Grone-Merris Conjecture.

Fall 2016

December 9 J. Sinkovic, C&O Dept., University of Waterloo Using eigenvalues to bound the independence number of graph
Abstract:    An independent set in a graph G is a set of pairwise non adjacent vertices and the maximum size of such a set is the independence number of G. A weight matrix W for a graph G is a symmetric (or Hermitian) matrix such that the (i,j) entry of W is zero whenever vertex i is not adjacent to vertex j. The Cvetkovic bound or inertia bound uses the eigenvalues of a weight matrix of G to give an upper bound on the independence number of a graph. We will introduce the bound, give a short proof, and discuss when the bound is tight. Until recently, it was open question as to whether the bound was always tight. Host: Michael Barrus.

December 2 E. Peterson, URI Building Spanning Trees Quickly in Maker-Breaker Games

November 18 J. Guillaume, URI A Tour of the Reconstruction Conjecture
Abstract:    The reconstruction conjecture is unequivocally one of the foremost open problems in graph theory. To start, we explore its background and history before stating it as a graph theory problem. Next, we dive into some important results regarding the conjecture, as well as different approaches considered and several variations of the problem. Finally, we take a look at what the future holds for the reconstruction conjecture and possible new directions that can be taken.

November 4 J. Jones, URI Report on 'How to Hunt an Invisible Rabbit on a Graph' by T. Abramovskaya, F. Fomin, P. Golovach, M. Pilipczuk

October 28 W. Kinnersley, URI Two variants of Cops and Robbers

October 21 A. Kodess, URI Algebraically defined digraphs

October 14 M. Barrus, URI Dense graphs and a conjecture for tree-depth
Abstract:    The tree-depth of a graph $G$ is the smallest number of ordered labels necessary to label the vertices of $G$ so that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is 1-unique if for each vertex $v$ in $G$, there is an optimal tree-depth-labeling of $G$ in which $v$ is the unique vertex receiving the lowest label. In a recent work the author and J. Sinkovic conjectured that all minor-minimal graphs having a fixed tree-depth are necessarily 1-unique. In this talk we study graphs with high tree-depths in relation to their orders. Using these results, a computer search, and a few interesting families of dense graphs, we resolve the 1-uniqueness conjecture and clarify relationships between 1-uniqueness and minor-minimality for tree-depth.

April 28	M. Williams, URI	Report on 'Unavoidable Induced Subgraphs in Large Graphs with no Homogeneous Sets' by M. Chudnovsky, R. Kim, S. Oum, P. Seymour
April 7	J. Erickson, URI	Waiter-Client and Client-Waiter Hamiltonicity Games on Random Graphs
		Abstract: The theory of positional games on graphs has developed into a highly studied area of combinatorics. In this talk, I'll explain the basics of two types of positional games played on graphs---the Waiter-Client and Client-Waiter games---and introduce the concepts of random graphs, expanders, and boosters. Then, I will use these topics to prove that when played on random graphs with the winning sets of the games being Hamiltonian cycles, we can derive sharp thresholds for players' winning strategies for these games. This is a report on 'Waiter-Client and Client-Waiter Hamiltonicity games on random graphs by D. Hefetz, M. Krivelevich, and W. Tan.
March 31	M. Kempton, CMSA, Harvard University	Non-backtracking Random Walks and Polya's Recurrence Theorem
		Abstract: The theory of random walks on graphs has become a major area of study in graph theory. Random walks are the basis for many important algorithms involving graphs in the real world, and there theory has been widely studied and is largely well-understood. In recent years, the study of non-backtracking random walks has gained interest, although their analysis has proven challenging. I will give some background on non-backtracking random walks on graphs, and present a non-backtracking version of a classical theorem in the theory of random walks on graphs: Polya's recurrence theorem. Host: Michael Barrus.
March 24	M. Barrus, URI	The Grone-Merris Conjecture
		Abstract: Spectral graph theory seeks to find relationships between the eigenvalues of a graph's adjacency matrix (or other related matrices) and the properties of the graph. In particular, in 1994 Grone and Merris conjectured a relationship between the degree sequence of an arbitrary graph $G$ and the eigenvalues of the Laplacian matrix of $G$. In this talk we introduce spectral graph theory, describe the relationship between degree sequences and eigenvalues, and present highlights of Hua Bai's 2011 proof of the Grone-Merris Conjecture.

December 9	J. Sinkovic, C&O Dept., University of Waterloo	Using eigenvalues to bound the independence number of graph
		Abstract: An independent set in a graph G is a set of pairwise non adjacent vertices and the maximum size of such a set is the independence number of G. A weight matrix W for a graph G is a symmetric (or Hermitian) matrix such that the (i,j) entry of W is zero whenever vertex i is not adjacent to vertex j. The Cvetkovic bound or inertia bound uses the eigenvalues of a weight matrix of G to give an upper bound on the independence number of a graph. We will introduce the bound, give a short proof, and discuss when the bound is tight. Until recently, it was open question as to whether the bound was always tight. Host: Michael Barrus.
December 2	E. Peterson, URI	Building Spanning Trees Quickly in Maker-Breaker Games
November 18	J. Guillaume, URI	A Tour of the Reconstruction Conjecture
		Abstract: The reconstruction conjecture is unequivocally one of the foremost open problems in graph theory. To start, we explore its background and history before stating it as a graph theory problem. Next, we dive into some important results regarding the conjecture, as well as different approaches considered and several variations of the problem. Finally, we take a look at what the future holds for the reconstruction conjecture and possible new directions that can be taken.
November 4	J. Jones, URI	Report on 'How to Hunt an Invisible Rabbit on a Graph' by T. Abramovskaya, F. Fomin, P. Golovach, M. Pilipczuk
October 28	W. Kinnersley, URI	Two variants of Cops and Robbers
October 21	A. Kodess, URI	Algebraically defined digraphs
October 14	M. Barrus, URI	Dense graphs and a conjecture for tree-depth
		Abstract: The tree-depth of a graph $G$ is the smallest number of ordered labels necessary to label the vertices of $G$ so that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is 1-unique if for each vertex $v$ in $G$, there is an optimal tree-depth-labeling of $G$ in which $v$ is the unique vertex receiving the lowest label. In a recent work the author and J. Sinkovic conjectured that all minor-minimal graphs having a fixed tree-depth are necessarily 1-unique. In this talk we study graphs with high tree-depths in relation to their orders. Using these results, a computer search, and a few interesting families of dense graphs, we resolve the 1-uniqueness conjecture and clarify relationships between 1-uniqueness and minor-minimality for tree-depth.