Brandeis Combinatorics Seminar -  Spring 2024

The Brandeis Combinatorics Seminar is an introductory seminar for combinatorics.
The talks should be (at least partially) understandable to first year graduate students.

The zoom link is  https://brandeis.zoom.us/j/94622483750

January 23:                 On Zoom!

Speaker: Eric Fusy (CNRS, Université Gustave Eiffel)

Title: Tamari intervals and blossoming trees

Abstract:  I will present a new bijection between intervals in the Tamari lattice and the blossoming trees  (Poulalhon and Schaeffer'06) that are in bijection to simple triangulations. Compared to the Bernardi-Bonichon bijection (composed with the Poulalhon-Schaeffer bijection), the effect of duality of Tamari intervals on the corresponding blossoming trees is very simple, making it possible to count self-dual intervals. Our bijection can be specialized to Kreweras intervals and synchronized intervals (as the Bernardi-Bonichon bijection), as well as modern/new intervals, and  infinitely modern intervals. It also reveals a new involution on Tamari intervals different from duality.

This is joint work with Wenjie Fang and Philippe Nadeau.

February 6: In person

Speaker: Shujian Chen (Brandeis)

Title: Generalized Goulden-Yong duals and signed minimal factorizations

Abstract:   In 2002, Goulden and Yong introduced a bijection between trees and minimal factorizations. I will first discuss how this result can be used to study signed minimal factorizations which is a refined enumeration of minimal factorizations. Then I will present the generalization of this bijection in type B and type D reflection groups as well as generalization of Prufer codes that are associated with trees.

This is joint work with Kiyoshi Igusa.

February 13: On Zoom

Speaker: Foster Tom (MIT)

Title: A signed $e$-expansion of the chromatic symmetric function and some new $e$-positive graphs

Abstract:  We prove a new signed elementary symmetric function expansion of the chromatic symmetric function of any unit interval graph. We then use sign-reversing involutions to prove new combinatorial formulas for many families of graphs, including the K-chains studied by Gebhard and Sagan, formed by joining cliques at single vertices, and for graphs obtained from them by removing any number of edges from any of the cut vertices. We also introduce a version for the quasisymmetric refinement of Shareshian and Wachs.

February 27: On Zoom

Speaker: Cosmin Pohoata (Emory University)

Title:  The Heilbronn triangle problem

Abstract:  Given an integer $n \geq 3$, the Heilbronn triangle problem asks for the smallest number $\Delta = \Delta(n)$ such that in every configuration of $n$ points in the unit square $[0,1]^2$ one can always find three among them which form a triangle of area at most $\Delta$. A trivial upper bound of the form $\Delta = O(1/n)$ follows from the simple observation that if one partitions $[0,1]^2$ into $n/2$ vertical strips of width $2/n$, then one of these strips must contain at least $3$ of the points. The problem of improving upon this basic observation is a difficult one, with a long history. In this talk, we will discuss some of this history along with some of the main ideas behind a recent new upper bound, showing that for sufficiently large $n$ in every configuration of $n$ points chosen inside a unit square there exists a triangle of area less than $n^{-8/7-1/2000}$. 

This is joint work with Alex Cohen and Dmitrii Zakharov.

March 5: In person

Speaker: Adam Zsolt Wagner (Worcester Polytechnic Institute)

Title: Reinforcement learning and pattern finding in combinatorics

Abstract:   We will look at two ways we can use tools from machine learning to help us with research in combinatorics. First we discuss reinforcement learning, a method that gives us a way to check conjectures for counterexamples efficiently. While it usually does not perform as well as other simpler methods, there have been several examples of projects in the past few years where RL was crucial for success. In the second half of the talk we will consider the following question of Ellenberg: at most how many points can we pick in the N by N grid, without creating an isosceles triangle? The best known constructions, found by computer searches for small values of N, clearly follow a pattern which we do not yet understand. We will discuss how one can train transformers to understand this pattern, and use this trained transformer to help us find a bit better constructions for various N.

This is joint work with Jordan Ellenberg, Marijn Heule, and Geordie Williamson

March 19: In person.

Speaker: Jonathan Boretsky (Harvard)

Title: The Nonnegative Tropical Flag Variety

Abstract:  The points of the flag variety of rank r=(r_1,…,r_k) has points corresponding are collections of subspaces (V_1,…,V_k) with V_i of dimension r_i such that V_i is contained in V_{i+1}. We explore two nonnegative versions of this variety: First, we study the nonnegative flag variety, which corresponds to a subset of the flag variety consisting of flags that can be represented by totally positive matrices. Second, we study the tropicalization of the flag variety and, more specifically, its nonnegative part. In both cases, we provide equivalent descriptions of these spaces for flag varieties of rank r=(a,a+1,\ldots,b), where r consists of consecutive integers. We explore the deep relationship between the nonnegative flag Dressian, flag positroids, and their polytopes. This talk is based on joint work with Chris Eur and Lauren Williams.

March 26: In person

Speaker: Emily Gunawan (UMass Lowell)

Title: Pattern-avoiding polytopes and Cambrian lattices

Abstract:  For each Coxeter element c in the symmetric group, we define a pattern-avoiding Birkhoff subpolytope whose vertices are the c-singletons. We show that the normalized volume of our polytope is equal to the number of longest chains in a corresponding type A Cambrian lattice. Our work extends a result of Davis and Sagan which states that the normalized volume of the convex hull of the 132 and 312 avoiding permutation matrices is the number of longest chains in the Tamari lattice, a special case of a type A Cambrian lattice. Furthermore, we prove that each of our polytopes is unimodularly equivalent to the (Stanley’s) order polytope of the heap H of the longest c-sorting word. The Hasse diagram of H is given by the Auslander - Reiten quiver for certain quiver representations. Our result gives an affirmative answer to a generalization of a question posed by Davis and Sagan. This talk is based on joint work with Esther Banaian, Sunita Chepuri, and Jianping Pan.

April 2: In person

Speaker: Colin Defant (Harvard)

Title: Bender--Knuth Billiards in Coxeter Groups 

Abstract:  Let (W,S) be a Coxeter system, and write S={s_i : i is in I}, where I is a finite index set. Consider a nonempty finite convex subset L of W. If W is a symmetric group, then L is the set of linear extensions of a poset, and there are important Bender--Knuth involutions BK_i (indexed by I) defined on L.  For arbitrary W and for each i in I, we introduce an operator \tau_i on W that we call a noninvertible Bender--Knuth toggle; this operator restricts to an involution on L that coincides with BK_i when W is a symmetric group. Given an ordering i_1,...,i_n of I and a starting element u_0 of W, we can repeatedly apply the toggles in the order \tau_{i_1},...,\tau_{i_n},\tau_{i_1},...,\tau_{i_n},.... This produces a sequence of elements of W that can be viewed in terms of a beam of light that bounces around in an arrangement of transparent windows and one-way mirrors. Our central questions concern whether or not the beam of light eventually ends up in the convex set L. We will discuss several situations where this occurs and several situations where it does not. This is based on joint work with Grant Barkley, Eliot Hodges, Noah Kravitz, and Mitchell Lee. 

April 9: In person

Speaker: Theo Douvropoulos (Brandeis)

Title: Hurwitz numbers via transportation polytopes

Abstract:   The classical Hurwitz numbers H_{g,k} enumerate, up to equivalence, branched coverings of the sphere by a genus g surface all of whose branch points are simple apart from a single one whose monodromy is given by the partition k. These numbers H_{g,k} are given via the ELSV formula as integrals over the moduli space of stable pointed curves \bar{M}_{g,n}, but explicit calculations are often difficult.

Under an equivalent interpretation, the Hurwitz numbers count certain so called transitive factorizations in S_n and classical representation-theoretic techniques describe their generating function via a finite sum of exponentials exp(t*m). The coefficients a_m that appear in this sum are integers and completely determine the enumeration.

Computational and theoretical evidence has led us to conjecture a description of these coefficients in terms of the h- and h*-vectors of certain transportation polytopes indexed by the partition k. We will present the conjecture and give proofs for certain cases, in part joint with Baptiste Louf and Guillaume Chapuy (in particular, for the identity partition k=(1^n) which corresponds to the central transportation polytope T_{n,n-1}). We will further give an equivalent formulation, where the answer for all partitions is simultaneously encoded in the equivariant Ehrhart theory of T_{n,n-1}.

Links to previous semesters: Fall2023, Spring2023, Fall 2022, Spring 2022, Fall 2021, Spring 2020, Fall 2019, Fall 2018, Spring 2018, Fall 2017, Spring 2017, Fall 2016, Spring 2016, Fall 2015, Spring 2015, Fall 2014, Spring 2014, Fall 2013.