Future students

Title: Intersections of graphs and χ-boundedness: Interval graphs, chordal graphs, and χ-guarding graph classes

Abstract: Following A. Gyárfás (1987), we say that a hereditary class of graphs is χ-bounded if there exists a function which provides an upper bound for the chromatic number of each graph of the class in terms of the graph's clique number. In this terminology, E. Asplund and B.Grünbaum (1960),  motivated by a question of A. Bielecski (1948), proved that the class of intersection graphs of axis parallel rectangles is χ-bounded, and J. P. Burling, in his Ph.D. thesis (1965), proved that the class of intersection graphs of axis parallel boxes in R^3 is not χ-bounded.

Title: Evolution of random representable matroids

There will be light refreshments starting at 3:00 pm.

Abstract: Inspired by the classical random graph process introduced by Erdos and Renyi in 1960, we introduce two analogous processes for random representable matroids. In the talk we address the following questions, with answers to some already established in existing literature, while others stem from recent research findings:

How does the rank of the random matroid evolve in the process?

When does the first k-circuit appear for each integer k? 

What is the length of the first circuit appearing in the process?

How does the connectivity of the matroid change?

What is the growth rate of the critical number (c.f. chromatic number of graphs) in the process?

When do given (small and large) matroid minors occur in the process?

How about the appearance of submatroids? 

Title: A Faster Combinatorial Algorithm for Maximum Bipartite Matching          

Abstract: The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp (1973) shows that maximum bipartite matching can be solved in $O(m \sqrt{n})$ time on a graph with $n$ vertices and $m$ edges. For the case of very dense graphs, a fast matrix multiplication based approach gives a running time of $O(n^{2.371})$. These results represented the fastest known algorithms for the problem until 2013, when Madry introduced a new approach based on continuous techniques achieving much faster runtime in sparse graphs.

Title: The limits of the inertia bound

Abstract: Spectral graph theory provides us with a wide array of surprising results which relate graph-theoretic parameters to linear-algebraic parameters of associated matrices. Among the most well-known and useful of these is Hoffman’s ratio bound, which gives an upper bound on the independence number of a graph in terms of its eigenvalues.

Title: A O(log log (rank) ) - competitive algorithm for the matroid secretary problem

Abstract: In the Matroid Secretary problem the weighted elements of a matroid arrive one by one in a uniformly random order where an online algorithm observes the value of the element and must make an irrevocable decision of whether or not to include the element in its solution before the arrival of the next element. The goal is to maximize the total value of the chosen elements under the condition that they must constitute an independent set. Other than knowing the cardinality of the ground set and having access to an independence oracle, the algorithm has no further information about the matroid.

Title: Odd cycle transversal in P5-free graphs

Abstract: Odd cycle transversal is a fun computational problem, somewhere between colouring and independent set: we are (equivalently) looking for a bipartite induced subgraph of maximum weight. As one might expect, this is NP-hard; I will tell you how to solve this problem in polynomial time in P5-free graphs (and more). Joint work with Cece Henderson, Evelyne Smith-Roberge, and Rebecca Whitman.

Note: I am COVID-cautious and will bring masks for those willing to wear them. 

Title: More Martin and c2 details.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.  Please also come to the pre-seminar to discuss what sorts of snacks and refreshments we might want going forward.

Abstract:  I'm going to tell you more of the details behind my Martin polynomial work last year with Erik Panzer which led to the proof of the c2 completion conjecture. I will actually describe the key bijection that proves it all, say some things about the permanent invariant, and cover other details that there hadn't been time for in the colloquium level presentation of the result.

Title: Subconstituents of Drackns 

Abstract: For a distance-regular graph X and an arbitrary vertex v, we often find interesting structure in the subgraph of X induced on vertices at distance 2 from v.

For example:

Any strongly-regular graph with parameters (n,k,a,k/2) can be found at distance 2 from a vertex in a distance-regular graph of diameter 3.

Certain distance-regular graphs of diameter 3 can be found at distance 2 from a vertex in a Moore graph of girth 5.

These (and more) examples are known as second-subconstituents, and they can be studied using the Terwilliger (or subconstituent) algebra of X. I will discuss this theory in the case that X is a distance-regular antipodal cover of a complete graph (drackn). This setting generalizes the first example and includes the second.

I will describe some general techniques for studying the Terwilliger algebras of drackns and then restrict to drackns without triangles. In this setting I will explain how to compute the spectrum of the second-subconstituent of any triangle-free drackn, except possibly the second-subconstituent OF a second-subconstituent of a Moore graph of valency 57.

We are pleased to announce a virtual workshop in honour of Chris Godsil's 75^th birthday. Chris Godsil's imprint on mathematics goes beyond algebraic combinatorics to merge theory and application, emerging research areas and well-developed mathematical tools. Chris Godsil is a research leader in discrete mathematics and he continues to be influential in a wide range of mathematical subdisciplines and communities around the world.  He has long been a prominent member of the Canadian combinatorial community, working first at Simon Fraser University and then playing a leadership role in the Department of Combinatorics and Optimization at the University of Waterloo; as a result, Chris Godsil has influenced multiple generations of mathematicians in Canada and abroad.

The goal of this workshop is not just to honour Chris Godsil's contributions and his impact on mathematics, but also to also bring together researchers in discrete math whose work has been influenced by Chris Godsil. We invite researchers in combinatorics, matrix theory, and quantum information theory from all over the world to join us, and will have sessions to accomodate a range of time zones.

Title: Online Edge Coloring with Tree Recurrences

Abstract: We will talk about online edge coloring in the edge arrival model. The vertex set V is known, and each edge arrives one by one, where it has to be colored irrevocably immediately. I will present the results from Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC 2022] which gives an algorithm that colors the graph with (e/e-1 + o(1))\delta colors.