Combinatorics Seminar - Spring 2020
When: Tuesday 3:30pm-4: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.
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.
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.
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.
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.
Speaker: John Wilmes (Brandeis)
Title: Counting Matchings with Markov Chain Monte Carlo
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.
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.
Speaker: Gleb Nenashev (MIT)
Speaker: GaYee Park (UMass Amherst)
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 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.
Speaker: Martin Tassy (Dartmouth)
Here are some indications for reaching Brandeis, and the math department.