Combinatorics Colloquium

Fall 2020

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.
Meeting Info: Via Zoom; for information, please contact Jozsef Balogh

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.
Meeting Info: Via Zoom; for information, please contact Alexander Yong

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.
Meeting Info:
 Via Zoom; for information, please contact Alexander Yong

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.
Meeting Info:
 Via Zoom; for information, please contact Jozsef Balogh

January 21, 2021 (time 3-4 pm CT)

Speaker: Stephanie van Willigenburg (U. British Columbia)
Title: The e-positivity of chromatic symmetric functions
The chromatic polynomial was generalized to the chromatic symmetric function by Stanley in his seminal 1995 paper. This function is currently experiencing a flourishing renaissance, in particular the study of the positivity of chromatic symmetric functions when expanded into the basis of elementary symmetric functions, that is, e-positivity.

In this talk we approach the question of e-positivity from various angles. Most pertinently we resolve the 1995 statement of Stanley that no known graph exists that is not contractible to the claw, and whose chromatic symmetric function is not e-positive.

This is joint work with Soojin Cho, Samantha Dahlberg, Angele Foley and Adrian She, and no prior knowledge is assumed.
Meeting Info:
 Via Zoom; for information, please contact Alexander Yong

February 18, 2021, 2-3 pm CT

Speaker: Hao Huang (Emory)
Title: TBA
Meeting Info:
 Via Zoom; for information, please contact Jozsef Balogh

Previous Colloquia

(information to come)