Combinatorics seminar
Combinatorics Seminar  Spring 2020
When: Tuesday 3:30pm4:30pm.
Where: Goldsmith 226.
Organizers: Olivier Bernardi and Duncan Levear
The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.

January 21
Speaker: Ira Gessel (Brandeis)
Title: Counting words with forbidden subwords
Abstract: I will talk about the GouldenJackson cluster theorem, which counts words by the number of occurrences of given words as (consecutive) subwords. As a consequence, the noncommutative generating function for words that avoid a set of subwords is the reciprocal of a series with every coefficient 0, 1, or 1, and this result is closely connected to a theorem of Curtis Greene on posets with Mobius function 0, 1, or 1.

February 4
Speaker: Annie Raymond (UMass Amherst)
Title: Simple Graph Density Inequalities with no Sum of Squares Proofs
Abstract: Establishing inequalities among graph densities is a central pursuit in extremal graph theory. One way to certify the nonnegativity of a graph density expression is to write it as a sum of squares or as a rational sum of squares. In this talk, we will explore how one does so and we will then identify simple conditions under which a graph density expression cannot be a sum of squares or a rational sum of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovász and Szegedy. This is joint work with Greg Blekherman, Mohit Singh, and Rekha Thomas.

February 11
Speaker: Olivier Bernardi (Brandeis)
Title: A Universal Tutte Polynomial
Abstract: Wouldn't it be nice to have a polynomial expression parametrizing at once the
Tutte polynomial of every matroid of a given size?
In this talk, I will explain how to achieve this goal. The solution involves extending the definition of the
Tutte polynomial from the setting of matroids to the setting of polymatroids
(this is akin to the generalization from graphs to hypergraphs), and adopting a geometric pointcounting perspective. On our way, we will connect several notions: the activitycounting invariants of Kalman
and Postnikov, the pointcounting invariants of Cameron and Fink, and the
classical coranknullity definition of the Tutte polynomial of matroids.
This is joint work with Tamas Kalman and Alex Postnikov.

February 25
Speaker: Yibo Gao (MIT)
Title: Separable elements and splittings of Weyl groups
Abstract: We introduce separable elements in finite Weyl groups, generalizing the wellstudied class of separable permutations. They enjoy nice properties in the weak Bruhat order, enumerate faces of the graph associahedron of the corresponding Dynkin diagrams, and can be characterized by pattern avoidance in the sense of Billey and Postnikov. We then prove that the multiplication map W/V x V > W for a generalized quotient of the symmetric group is always surjective when V is a principal order ideal, providing the first combinatorial proof of an inequality due originally to Sidorenko in 1991, answering an open problem of Morales, Pak, and Panova. We show that this multiplication map is a bijection if and only if V is an order ideal in the right weak order generated by a separable element, answering an open question of Björner and Wachs in 1988. This is joint work with Christian Gaetz.

March 3
Speaker: John Wilmes (Brandeis)
Title: Counting Matchings with Markov Chain Monte Carlo
Abstract:
Perfect matchings pair each vertex in a graph with exactly one adjacent vertex. The algorithmic
problem of counting all perfect matchings in a bipartite graph is famously intractableit is the
prototypical #Pcomplete problem. Nevertheless, a randomized algorithm due to Jerrum, Sinclair,
and Vigoda can efficiently approximately count the number of perfect matchings in a bipartite
graph, via a classic application of the Markov Chain Monte Carlo (MCMC) technique. We will take a
brief tour through matching theory, computational complexity, and MCMC for sampling and counting
combinatorial structures, before describing recent progress on related problems.

March 10
Speaker: Zilin Jiang (MIT)
Title: : The colorful world of rainbow sets
Abstract: Given a (finite) family of structures, is it possible to choose an element from each structure to form a new structure of the same kind? This new structure is poetically called rainbow for we can think of each given structure is in a different color. Some longstanding combinatorial problems, such as transversals in a Latin square and the CaccettaHaggkvist conjecture, are rainbow in nature. In this talk, we will discuss such problems where the structures are (a) subsets in R^d which contain 0 in their convex hulls; (b) matchings; (c) paths / cycles in a digraph; and (d) cycles (or odd cycles) in a graph.

March 17
Speaker: Gleb Nenashev (MIT)
Title: TBD
Abstract:

March 24
Speaker: GaYee Park (UMass Amherst)
Title:
Abstract:

March 31
Speaker: Nadia Lafreniere (Dartmouth)
Title: Eigenvalues of the symmetrized shuffling operators
Abstract: When looking at a procedure for shuffling a deck of cards, one can ask for the necessary and sufficient amount of time one needs to repeat it so that the deck is well shuffled. An important statistics in the study of that question is the eigenvalues of a Markov chain. For a given shuffle, that Markov chain is build on the state space of arrangements of the deck (the permutations).
The randomtorandom shuffle corresponds to removing one card (randomly) and placing it back into the deck at a random place. In this talk, I will build the Markov chains for shuffling techniques similar to randomtorandom called the symmetrized shuffling operators, and introduced by Victor Reiner, Franco Saliola and Volkmar Welker in 2014. I will show that their eigenvalues are all nonnegative integers by writing them as statistics on combinatorial objects called standard tableaux. I will present some conjectures on the mixing time, that are likely to be proven using the eigenvalues.

April 21
Speaker: Martin Tassy (Dartmouth)
Title: TBD
Abstract:
Here are some indications for reaching Brandeis, and the math department.
Previous semesters:
Fall 2019,
Fall 2018,
Spring 2018,
Fall 2017,
Spring 2017,
Fall 2016,
Spring 2016,
Fall 2015,
Spring 2015,
Fall 2014,
Spring 2014,
Fall 2013.