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 Goulden-Jackson 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 point-counting perspective. On our way, we will connect several notions: the activity-counting invariants of Kalman and Postnikov, the point-counting invariants of Cameron and Fink, and the classical corank-nullity 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 well-studied 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 intractable---it is the prototypical #P-complete 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 Caccetta--Haggkvist 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) -- CANCELED (COVID19)
  Title: Differential operators on Schur and Schubert polynomials
  Abstract: TBD
  
  
  
  

• March 24

  Speaker: GaYee Park (UMass Amherst) -- CANCELED (COVID19)
  Title: TBD
  Abstract:
  
  
  
  

• March 31

  Speaker: Nadia Lafreniere (Dartmouth) -- CANCELED (COVID19)
  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 random-to-random 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 random-to-random 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 non-negative 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) -- CANCELED (COVID19)
  Title: TBD
  Abstract: