Fall 2020 Combinatorics Colloquia

September 10, 2020 4-5pm CT (Joint with the Mathematics Colloquium)

Speaker: Noga Alon (Princeton and Tel Aviv)
Title: Fair representation
Abstract: A substantial number of results and conjectures deal with the existence of a set of prescribed type which contains a fair share from each member of a finite collection of objects in a space. Examples include the Ham-Sandwich Theorem in Measure Theory, the Hobby-Rice Theorem in Approximation Theory, the Necklace Theorem and the Ryser Conjecture in Discrete Mathematics, and more. The techniques in the study of these results combine combinatorial, topological, geometric and algebraic tools. I will describe the topic, focusing on several recent results.

October 1, 2020 3-4pm CT

Speaker: Hugh Thomas (University of Quebec at Montreal)
Title: The fundamental theorem of finite semi-distributive 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 theorem characterizing finite semidistributive lattices, formally similar to the fundamental theorem of finite distributive lattices. In a 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.

November 5, 2020, 4-5 pm CT (Joint with the Mathematics Colloquium)

Speaker: Greta Panova (U. Southern California)
Title: Computational Complexity meets Algebraic Combinatorics
How hard is a problem? How nice is a solution? Such questions can actually be formalized using the theory of Computational Complexity. Yet, distinguishing the different computational complexity classes, like P vs NP, are major problems. Algebraic Combinatorics studies discrete structures originating in Algebra/Representation Theory via combinatorial methods and vice versa. Some of the main longstanding open problems concern the “combinatorial interpretation” of structure constants and multiplicities originally defined via representation theory like Kronecker and plethysm coefficients. In this talk we will discuss the two-way interaction between the fields via such structure constants. First, how Kronecker coefficients appear in the distinction of algebraic complexity classes via the Geometric Complexity Theory. Second, how computational complexity explains why the problem of finding a combinatorial interpretation is hard.


December 10, 2020, 10-11 am CT

Speaker: Maria Chudnovsky (Princeton)
Title: Induced subgraphs and tree decompositions
Tree decompositions are a powerful tool in structural graph
theory, that is traditionally used in the context of forbidden graph minors.
Connecting tree decompositions and forbidden induced subgraphs has so far
remained out of reach. Recently we obtained several results in this direction;
the talk will be a survey of these results.