Brandeis Combinatorics Seminar - Spring 2022

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/92650710647

Please email the organizers if you would like to know the password.

January 25:

Speaker: Nadia Lafrenière (Dartmouth)

Title: The spectrum of the random-to-below Markov chain

Abstract: The random-to-below shuffle of a deck of cards consists of removing any card randomly (with uniform probability), and inserting it anywhere below (with uniform probability). When looking at the eigenvalues of its transition matrix, they all seem to be rational and positive. This is surprising for a non-symmetric matrix, and suggests some combinatorial interpretation. We discuss some ongoing attempts at giving a recursive explanation that involves standard Young tableaux, and makes connection with the well studied top-to-random shuffle. We finally describe a more straightforward way to compute a stopping time for this shuffle, answering the question of how long we would need to shuffle to get a well-mixed deck using this shuffling technique.

February 1:

Speaker: Michael Simkin (Harvard)

Title: The number of n-queens configurations

Abstract: The n-queens problem is to determine Q(n), the number of ways to place n mutually non-threatening queens on an n x n board. We show that there exists a constant 1.94 < a < 1.9449 such that Q(n) = ((1 + o(1))ne^(-a))^n. The constant a is characterized as the solution to a convex optimization problem in P([-1/2,1/2]^2), the space of Borel probability measures on the square.

The chief innovation is the introduction of limit objects for n-queens configurations, which we call "queenons". These are a convex set in P([-1/2,1/2]^2). We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons.

February 8:

Speaker: Eric Fusy (CNRS, Universite Marne-la-Vallee)

Title: Maps of unfixed genus and blossoming trees

Abstract: 4-regular planar maps can be counted bijectively via two constructions: one with blossoming trees due to Schaeffer, and one with well-labeled trees due to Cori-Vauquelin-Schaeffer.

As shown by Bouttier, Di Francesco, and Guitter, these bijections imply that the so-called 2-point function R_i(t) of 4-regular planar maps (generating function of 4-regular maps with two points at dual distance smaller than i) satisfies the recurrence R_i(t)=1+R_i(t)*(R_{i-1}(t)+R_i(t)+R_{i+1}(t)) (with boundary condition R_0(t)=0), which remarkably can be solved explicitly.

I will show how the construction based on blossoming trees can be extended to 4-regular maps of unfixed genus. This provides a bijective proof of the fact that the corresponding counting series is expressed as the first term r_1(t) of a sequence of series (r_i(t))_{i\geq 1} that are now related by the recurrence r_i(t)=i+r_i(t)*(r_{i-1}(t)+r_i(t)+r_{i+1}(t)), with boundary condition r_0(t)=0 (this is the same recurrence as for the R_i(t), except for the constant term i instead of 1), an expression that had previously been obtained via the configuration model and matrix integrals. Our construction (which crucially relies on results by Olivier Bernardi on the link between certain orientations of maps and their spanning trees) also contains the one for 4-regular planar maps, and it explains the similarity between the series expressions for the planar case and the unfixed genus case.

This is joint work with Emmanuel Guitter

February 15:

Speaker: Shizhe Liang (Brandeis)

Title: Grand-Schnyder decompositions and applications to drawing

Abstract: In 1990, Schnyder showed that every plane triangulation admits a special partition of its inner edges into 3 trees, which are known as the Schnyder woods. Using this structure, Schnyder designed a straight-line grid drawing algorithm for triangulations. Since then, other structures and algorithms sharing the same flavor were found by various authors.

In this talk I will be presenting a new general construction, named grand-Schnyder decomposition, that simultaneously generalizes several of these structures (notably the original Schnyder woods, the regular edge labelings of Kant and He, and the d-Schnyder structures of Bernardi and Fusy). Precisely, a grand-Schnyder decomposition of parameter d is defined on a plane graph with an outer face of degree d and inner faces of degree d-1 or d. It is a set of d spanning forests crossing each other in a specific way, so that each inner edge is in either d-2, d-3 or d-4 of the spanning forests. Such a structure exists if and only if the non-facial girth of the underlying graph is at least d.

Using grand-Schnyder decompositions of parameter d=4 we provide a general framework of drawing algorithms, which unifies existing algorithms due to Kant and He, Fusy, Barriere & Huemer, and Bernardi & Fusy.

This is a joint work with Olivier Bernardi and Eric Fusy.

March 1:

Speaker: Greta Panova (University of Southern California)

Title: Hook formulas for skew shapes and beyond

Abstract: The hook length formula for  the number of Standard Young Tableaux of a partition lambda is one of the few miraculous product formulas we see in combinatorics. While no such formula for the number of skew SYTs exists in general, the recent Naruse Hook Length Formula (NHLF) brings us close. I will explain this formula and generalizations, give some proofs and bijections, and discuss new extensions of NHLF for increasing tableaux originating in the study of Grothendieck polynomials. 

Based on a series of papers with A. Morales and I. Pak.

March 8:

Speaker: Sam Hopkins (Howard University)

Title: Enumeration of barely set-valued tableaux and plane partitions

Abstract: The Hook Length Formula for the number of standard Young tableaux of given shape is a deservedly celebrated result in modern enumerative and algebraic combinatorics. There is great interest in obtaining product formulas for the enumeration of other classes of tableaux, and other related 2D arrays of numbers like plane partitions. We will survey recent work which gives product formulas (and even q-analogs) for counting certain "barely set-valued" arrays.

March 15:

Speaker: Andrew Gitlin (UC Berkeley)

Title: A vertex model for LLT polynomials and k-tilings of the Aztec diamond

Abstract: We describe a Yang-Baxter integrable colored vertex model, from which we construct a class of partition functions that equal the LLT polynomials of Lascoux, Leclerc, and Thibon. Using the vertex model formalism, we can prove many properties of these polynomials, including symmetry and a Cauchy identity.

We also use the vertex model to study k-tilings (k-tuples of domino tilings) of the Aztec diamond of rank m, where we assign a weight to each k-tiling depending on the number of vertical dominos and the number of "interactions" between the tilings. We compute the generating polynomials of the k-tilings, and prove some combinatorial results about k-tilings in certain limits of the interaction strength.

March 22:

Speaker: Lilla Tóthmérész ( Eötvös Loránd University)

Title: Dissecting graph polytopes using a combinatorial embedding

Abstract: The root polytope of a graph is a polytope introduced by Postnikov, whose geometry reflects interesting graph properties.

In 2006, Bernardi gave a family of bijections between the spanning trees of a graph G and the break divisors of the chip-firing game, using a combinatorial embedding of the graph. Let Bip G be the bipartite graph obtained from G by subdividing each edge with a new vertex, and let the two color classes of the obtained bipartite graph be called V and E. Then the above bijection is equivalent to a bijection between the degree sequences on E and on V that are realizable by spanning trees.

We generalize this bijection to all bipartite graphs, and show that it corresponds to a dissection of the root polytope into simplices. Moreover, this dissection is shellable, and the h-vector is related to embedding activities.

We show that (once again, using a combinatorial embedding) one can give a similar shellable dissection of the root polytope of a directed graph, given that each cycle has the same number of edges pointing in the two cyclic directions.

Then we point out that with this method, one can also give a shellable dissection for the symmetric edge polytope of a graph. The terms of the h-vector can also be described using graph theory in this case.

Joint work with Tamás Kálmán.

March 29:

Speaker: Karola Meszaros (Cornell University)

Title: Schur and related polynomials through a discrete geometric lens

Abstract: In this talk we'll take a discrete geometric view of classical polynomials, such as Schur polynomials, and their more recent generalizations: the Schubert and Grothendieck polynomials, via their Newton polytopes. We will explore questions that the geometric viewpoint inspires, and time permitting we will also discuss how certain Schubert polynomials arise from triangulations of flow polytopes. We will aim to give many examples and will assume no specific background other than being comfortable with discrete geometry and combinatorics.

April 5:

Speaker: Ira Gessel (Brandeis)

Title: Congruences for middle binomial coefficient sums

Abstract: I will discuss some congruences for partial sums of middle binomial coefficients (and Catalan numbers) to prime and prime power moduli. These congruences have been studied by a number of combinatorialists, and the approaches I will discuss are interesting applications of generating functions.



April 12:

Speaker: Gleb Nenashev (Brandeis)

Title: The Maximum Multiplicity of a Generator in a Reduced Word.

Abstract: We study the maximum multiplicity M(k,n) of a simple transposition (k k+1) in a reduced word for the longest permutation, a problem closely related to much previous work on sorting networks and on the “k-sets" problem. After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed k and growing n, the optimal collections are periodic in a precise sense, so that M(k,n)=cn+p(n) for a periodic p and constant c. Furthermore, we show that c is rational for every k.

April 26:

Speaker: Spencer Backman (University of Vermont)

Title: Higher Categorical Associahedra

Abstract: The associahedron is a well-known polytope with connections to many different areas of combinatorics, algebra, geometry, topology, and physics. The associahedron has Catalan number many vertices which can be equivalently described in terms of triangulations of a polygon, planar binary trees, maximal parenthesizations of a word, etc. From one perspective, the associahedron encodes the combinatorics of morphisms in the Fukaya category of a symplectic manifold. In 2017, Bottman introduced a combinatorially defined family of posets called 2-associahedra which encode the combinatorics of functors between Fukaya categories, and he conjectured that they can be realized as the face posets of convex polytopes. In this talk, I will begin by reviewing the basic theory of associahedra. I will then introduce n-associahedra as a natural extension of associahedra and 2-associahedra, and I will produce a family of complete polyhedral fans called velocity fans whose face posets are the n-associahedra. This is joint work with Nathaniel Bottman and Daria Poliakova.

Links to previous semesters: 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.