Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2020

March 04 A. Bonato, Ryerson University What we know and don't know about the cop number of a graph

Abstract: The game of Cops and Robbers played on graphs gives rise to a rich theory focusing on the cop number of a graph. While we possess a good structural and algorithmic understanding of the cop number for many graph families, Meyniel's conjecture and Schroeder's conjecture point to our limited understanding of this parameter. We give an overview of major results and conjectures on the cop number of graphs, and consider recent variants such as Lazy Cops and Robbers, Zombies and Survivors, and the localization game.
Host: W. Kinnersley

Fall 2019

November 08 M. Barrus, URI Characterizing graphs with nice matrix cokernels
Abstract:    Many interesting properties of a graph $G$ can be deduced from properties of its adjacency matrix $A(G)$ or its Laplacian matrix $L(G)$. Turning things around, notable properties of the matrices sometimes correspond to graphs having other nice characterizations. In this report on an ongoing project with C. Alfaro, J. Sinkovic, and R. Villagran, I will give a gentle introduction to the Smith group and critical group of a graph, both defined in terms of the cokernels of $A(G)$ and $L(G)$ when considered as linear maps (no familiarity with these concepts will be assumed). It turns out that when one or the other of these groups is required to have few trivial invariant factors or characteristic ideals, the corresponding graphs have forbidden induced subgraph characterizations. I will present a characterization for one of these families and discuss ongoing work on characterizing the other.

October 25 A. Ferber, MIT Resilience for perfect matchings in random hypergraphs
Abstract:    Let $m_d(k,n)$ be the smallest integer $m$ for which every $k$-uniform hypergraph on $n$ vertices and with minimum $d$-degree at least $m$ contain a perfect matching (we always assume that $n$ is divisible by $k$). The problem of determining $m_d(k,n)$ has attracted a lot of attention in the last few decades. Quite surprisingly, this problem is still wide open, and have led to the development of many techniques and interesting connections with other areas.
Recently, there has been interest in extending extremal theorems to random environments. In our setting, we are interested in finding minimum degree conditions for the existence of a perfect matching in subgraphs of a typical random hypergraph $H^k_{n,p}$. We prove that for $p\geq C\max\{n^{-k/2+\epsilon},n^{-k+d+1}\}$, a typical $H^k_{n,p}$ is such that every subgraph $G\subseteq H$ with minimum $d$-degree at least $(1+o(1))m_d(k,n)$ contains a perfect matching. Note that this holds for all $d,k$ even in cases when the exact value of $m_d(k,n)$ is unknown. Our proof is based on a new ``non-constructive" absorbers technique which we believe is of independent interest.
Joint work with Matthew Kwan.
Host J. Han.

September 20 A. Sidorenko Integral and matrix inequalities associated with graphs
Abstract:    pdf

September 13 J. Han, URI Zero-nonzero patterns that allow $S_n^*$
Abstract:    For $n\ge 2$, let $S_n^*=\{(0,n,0), (0,n-1,1), (1,n-1,0), (n,0,0), (n-1,0,1), (n-1,1,0)\}$. An n by n zero-nonzero pattern A allows $S_n^*$ if $\mathbb{S}_n^* \subseteq i(A)$, namely, there exist (six) real matrices that realize each of the inertias separately. In this talk we study zero-nonzero patterns that allow $S_n^*$.

March 04	A. Bonato, Ryerson University	What we know and don't know about the cop number of a graph
		Abstract: The game of Cops and Robbers played on graphs gives rise to a rich theory focusing on the cop number of a graph. While we possess a good structural and algorithmic understanding of the cop number for many graph families, Meyniel's conjecture and Schroeder's conjecture point to our limited understanding of this parameter. We give an overview of major results and conjectures on the cop number of graphs, and consider recent variants such as Lazy Cops and Robbers, Zombies and Survivors, and the localization game. Host: W. Kinnersley

November 08	M. Barrus, URI	Characterizing graphs with nice matrix cokernels
		Abstract: Many interesting properties of a graph $G$ can be deduced from properties of its adjacency matrix $A(G)$ or its Laplacian matrix $L(G)$. Turning things around, notable properties of the matrices sometimes correspond to graphs having other nice characterizations. In this report on an ongoing project with C. Alfaro, J. Sinkovic, and R. Villagran, I will give a gentle introduction to the Smith group and critical group of a graph, both defined in terms of the cokernels of $A(G)$ and $L(G)$ when considered as linear maps (no familiarity with these concepts will be assumed). It turns out that when one or the other of these groups is required to have few trivial invariant factors or characteristic ideals, the corresponding graphs have forbidden induced subgraph characterizations. I will present a characterization for one of these families and discuss ongoing work on characterizing the other.
October 25	A. Ferber, MIT	Resilience for perfect matchings in random hypergraphs
		Abstract: Let $m_d(k,n)$ be the smallest integer $m$ for which every $k$-uniform hypergraph on $n$ vertices and with minimum $d$-degree at least $m$ contain a perfect matching (we always assume that $n$ is divisible by $k$). The problem of determining $m_d(k,n)$ has attracted a lot of attention in the last few decades. Quite surprisingly, this problem is still wide open, and have led to the development of many techniques and interesting connections with other areas. Recently, there has been interest in extending extremal theorems to random environments. In our setting, we are interested in finding minimum degree conditions for the existence of a perfect matching in subgraphs of a typical random hypergraph $H^k_{n,p}$. We prove that for $p\geq C\max\{n^{-k/2+\epsilon},n^{-k+d+1}\}$, a typical $H^k_{n,p}$ is such that every subgraph $G\subseteq H$ with minimum $d$-degree at least $(1+o(1))m_d(k,n)$ contains a perfect matching. Note that this holds for all $d,k$ even in cases when the exact value of $m_d(k,n)$ is unknown. Our proof is based on a new ``non-constructive" absorbers technique which we believe is of independent interest. Joint work with Matthew Kwan. Host J. Han.
September 20	A. Sidorenko	Integral and matrix inequalities associated with graphs
		Abstract: pdf
September 13	J. Han, URI	Zero-nonzero patterns that allow $S_n^*$
		Abstract: For $n\ge 2$, let $S_n^=\{(0,n,0), (0,n-1,1), (1,n-1,0), (n,0,0), (n-1,0,1), (n-1,1,0)\}$. An n by n zero-nonzero pattern A allows $S_n^$ if $\mathbb{S}_n^* \subseteq i(A)$, namely, there exist (six) real matrices that realize each of the inertias separately. In this talk we study zero-nonzero patterns that allow $S_n^*$.