Current students

Title: Edge Deletion-Contraction in the Chromatic and Tutte Symmetric Functions

Abstract:

We consider symmetric function analogues of the chromatic and Tutte polynomials on graphs whose vertices have positive integer weights. We show that in this setting these functions admit edge deletion-contraction relations akin to those of the corresponding polynomials, and we use these relations to give enumerative and/or inductive proofs of properties of these functions.

The profound impact of early discovery, experimentation, and disruption through research and invention

Researchers today build on the knowledge and discoveries made by those who have come before them. How can today’s researchers light the early pathways and curiosities for the research breakthroughs of the future? How can we demonstrate the impact and potential of the yet-to-be known? And, what if any, role does academia, industry, the Faculty of Mathematics, and Canada play in increasing the discovery journey to these new frontiers?

Title: Further progress towards Hadwiger's conjecture

Abstract:

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. 

Title: Projective Planes, Finite and Infinite

Abstract:

A projective plane is a point-line incidence structure in which every pair of distinct points has a unique joining line, and every pair of distinct lines meets in a unique point. Equivalently (as described by its incidence graph), it is a bipartite graph of diameter 3 and girth 6. 

Title: Scaffolds

Abstract:

Building on the work of various authors who have used tensors in the study of association schemes and spin models, I propose the term "scaffold" for certain tensors that have been represented by what are sometimes called "star-triangle diagrams" in the literature. The main goal of the talk is to introduce and motivate these objects which somewhat resemble partition functions as they appear in combinatorics. (The exact definition is too cumbersome to include here.)

Title: Recent proximity results in integer linear programming

Abstract:

We consider the proximity question in integer linear programming (ILP) --- Given a vector in a polyhedron, how close is the nearest integer vector? Proximity has been studied for decades with two influential results due to Cook et al. in 1986 and Eisenbrand and Weismantel in 2018. We derive new upper bounds on proximity using sparse integer solutions and mixed integer relaxations of the integer hull. When compared to previous bounds, these new bounds depend less on the dimensions of the constraint matrix and more on the data in the matrix.

Title: Laplacian Quantum Fractional Revival On Graphs

Abstract:

Given a set of quantum bits, we can model their interactions using graphs. The continuous-time quantum walks on a graph can be viewed as the Schrödinger dynamics of a particle hopping between adjacent vertices. In this talk, the transition matrix of the continuous-time quantum walk is given by $e^{-itL}$, where $L$ is the graph’s Laplacian matrix.

Title: Pure pairs

Abstract:

A pure pair in a graph G is a pair of subsets A and B of the vertex set such that between A and B, either all edges or no edges are present in G. This concept was first introduced in connected with the Erdos-Hajnal conjecture, but has since developed a life of its own. I will give an overview of results and open questions on pure pairs.

Based on joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.

Title: State transfer and the size of the graph

Abstract:

If there is perfect state transfer between two vertices at distance d, how small can the graph be compared to d? This question is motivated by the fact that the known infinite families of graphs admitting state transfer at increasingly large distances are all obtained from graph products, thus their sizes grow exponentially compared to their diameter.