Discrete Mathematics and Optimization Seminar

March 14th 2020: Due to the COVID-19 pandemic and the school closure, we are cancelling all meetings until further notice.

Time and place: Wednesday 1:15-2:05pm in Burnside 1104

Organised by Stefan Grosser, Ndiamé Ndiaye and Youri Tamitegama. For more information or if you would like to present, feel free to contact any of us at "first.last@mail.mcgill.ca".

To subscribe to the mailing list, please fill in this form.

Talks for Winter 2020

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.