To subscribe to the mailing list, please fill in this form.
January 22nd, Sergey Norin, McGill University
Title: Relaxations of Hadwiger's conjecture
Abstract: Hadwiger's conjecture from 1943 states that every simple graph with no Kt minor can be properly colored using t-1 colors. This is a far-reaching strengthening of the four-color theorem, and appears to be currently out of reach in its full generality. I will survey related results, in particular, two relaxations of the conjecture established recently jointly with Zdenek Dvorak, and with Luke Postle and Zi-Xia Song.
-----------------------------
January 29th, Stefan Grosser, McGill University
Title: Counting Linear Extensions of Posets with Determinants of Hook Lengths
Abstract: The classical problem of counting linear extensions asks how many ways a partially order set can be filled in to become a total order. It is known to be #P-complete in general, but it can be efficiently computed for certain special classes of posets. We survey these results, and introduce a new class of posets that have determinant formulas to count their linear extensions. This is joint work with Alexander Garver, Jacob Matherne, and Alejandro Morales.
-----------------------------
February 5th, No meeting due to the optimization job talks.
-----------------------------
February 12th, Hamed Hatami, McGill University
Title: Sign rank vs approximate rank
Abstract: Sign-rank and approximate rank are two central notions in communication complexity and matrix theory. In this talk I will prove the strongest possible separation by constructing a Boolean matrix whose sign-rank is only 3, and yet its approximate rank is linear. The proof uses some tools and ideas from analytic number theory. This is based on a joint work with Kaave Hosseini and Shachar Lovett.
-----------------------------
February 19th, Hugh Thomas, Université du Québec à Montréal
Title: The fundamental theorem of finite semidistributive lattices
Abstract: The fundamental theorem of finite distributive lattices of Birkhoff says that any finite distributive lattice can be realized as the set of order ideals of a poset, ordered by inclusion. Semidistributive lattices are a generalization of distributive lattices, introduced by Jónsson in the 60s; he showed that free lattices are semidistributive. Among the interesting examples of finite semidistributive lattices are weak order on finite Coxeter groups and the torsion classes of an algebra (supposing there are only finitely many). I will present a fundamental theorem of finite semidistributive lattices, formally similar to the fundamental theorem of finite distributive lattices. In some sense, this is a combinatorialization of the structure of torsion classes, but our construction does not actually use any representation theory, and I will not assume any knowledge of representation theory in my talk. This talk is based on arXiv:1907.08050, joint with Nathan Reading and David Speyer.
-----------------------------
February 26th, Krystal Guo, Université de Montréal
Title: Transversal polynomial of covers of graphs
Abstract: We explore the interplay between algebraic combinatorics and some algorithmic problems in graph theory. We define a polynomial with connections to correspondence colouring, a recent generalization of list-colouring, and the Unique Games Conjecture. Like the chromatic polynomial of a graph, we are able to evaluate this polynomial at -r+1 modulo rn, despite the complexity of computing this polynomial. This is based on joint work with Chris Godsil and Gordon Royle.
-----------------------------
March 4th, Reading week
-----------------------------
March 11th, Alp Müyesser, Freie Universität Berlin
Title: Ramsey and Turan type problems on colored graphs
Abstract: Ramsey's theorem roughly states that any graph on sufficiently many vertices will contain a large monochromatic pattern. Here, we investigate the emergence of multicolored patterns under the assumption that all colors in the host graph are well-represented. In particular, we will discuss the Turan analogue of a problem of Bollobas which states that any balanced red-blue coloring of a large enough complete graph contains a large k-unavoidable graph, that is, a red-blue coloring of a K2k where one color class forms a clique of size k, or two cliques of size k each. An example theorem will be that any graph with density 1-1/k and edges colored half red half blue will contain a clique on k-O(1) vertices with a red as well as a blue edge. This extends a result of DeVos et al. about triangles to cliques of arbitrary size. This is based on joint works with Boris Bukh and Mike Tait.
-----------------------------