Talk_id  Date  Speaker  Title 
26940

Wednesday 1/20 3:00 PM

Sergi Elizalde, Dartmouth College

Descents on quasiStirling permutations
 Sergi Elizalde, Dartmouth College
 Descents on quasiStirling permutations
 01/20/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
Stirling permutations were introduced by Gessel and Stanley to give a combinatorial interpretation of certain polynomials related to Stirling numbers. A very natural extension of Stirling permutations are quasiStirling permutations, which are in bijection with labeled rooted plane trees. Archer et al. introduced these permutations, and conjectured that there are $(n+1)^{n1}$ quasiStirling permutations of size $n$ having $n$ descents.
In this talk we prove this conjecture. More generally, we give the generating function for quasiStirling permutations by the number of descents, which turns out to satisfy a beautiful equation involving Eulerian polynomials. We show that some of the properties of descents on usual permutations and on Stirling permutations have an analogue for quasiStirling permutations.
Finally, we extend our results to a oneparameter family of permutations, called $k$quasiStirling permutations, which are in bijection with certain decorated trees.

26941

Wednesday 1/27 3:00 PM

Joshua Swanson, UCSD

DUSTPAN distributions as limit laws for Mahonian statistics on forests
 Joshua Swanson, UCSD
 DUSTPAN distributions as limit laws for Mahonian statistics on forests
 01/27/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
Building on work of Stanley and BjörnerWachs, we study the distribution of certain Mahonian statistics on several families of posets, including the major index on linear extensions of forests. We show that the resulting standardized distributions are often asymptotically normal. However, in certain regimes, we must introduce a new, closed family of continuous probability distributions called DUSTPAN distributions which simultaneously generalize the IrwinHall and normal distributions. In the case of forests, we use graphtheoretic statistics like height and elevation to completely determine the precise limit laws. This leads to some natural open questions about the distribution of the height of such forests.
Joint work with Sara Billey (https://arxiv.org/abs/2010.12701) building on earlier joint work with Sara Billey and Matjaž Konvalinka (https://arxiv.org/abs/1905.00975).

26975

Wednesday 2/3 3:00 PM

Richard Stanley, MIT

Two Analogues of Pascal's Triangle
 Richard Stanley, MIT
 Two Analogues of Pascal's Triangle
 02/03/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
Pascal's triangle is closely associated with the expansion of
the product $(1+x)^n$. We will discuss two analogous arrays of numbers
that are associated with the products
$\prod_{i=0}^{n1} \left(1+x^{2^i}+x^{2^{i+1}}\right)$ and
$\prod_{i=1}^n \left(1+x^{F_{i+1}}\right)$, where $F_{i+1}$ is a Fibonacci
number. All three arrays are special cases of a twoparameter family that
might be interesting to investigate further.

26995

Wednesday 2/10 3:00 PM

Nicholas Ovenhouse, University of Minnesota

Laurent Polynomials from the Super Ptolemy Relation
 Nicholas Ovenhouse, University of Minnesota
 Laurent Polynomials from the Super Ptolemy Relation
 02/10/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
In classical geometry, Ptolemy's theorem relates the lengths of the sides of a quadrilateral to the lengths of the diagonals. Fixing a triangulation of a polygon, the length of any diagonal can be expressed (using Ptolemy's theorem) as a Laurent polynomial in the lengths of diagonals in the triangulation. There is a combinatorial description of the terms in this Laurent polynomial due to Schiffler, in terms of "Tpaths". Recently, Penner and Zeitlin constructed a superalgebra from a triangulation, and an analogue of the Ptolemy relation in this situation. I will describe a generalization of "Tpaths" which enumerate the terms in the corresponding super Laurent polynomials. This is joint work with Gregg Musiker and Sylvester Zhang.

27000

Wednesday 2/17 3:00 PM

Tom Roby, University of Connecticut

An actionpacked introduction to homomesy
 Tom Roby, University of Connecticut
 An actionpacked introduction to homomesy
 02/17/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
Dynamical Algebraic Combinatorics explores maps on sets of discrete combinatorial objects with particular attention to their orbit structure. Interesting counting questions immediately arise: How many orbits are there? What are their sizes? What is the period of the map if it's invertible? Are there any interesting statistics on the objects that are wellbehaved under the map?
One particular phenomenon of interest is ``homomesy'', where a statistic on the set of objects has the same average for each orbit of an action. Along with its intrinsic interest as a kind of hidden ``invariant'', homomesy can be used to help understand certain properties of the action. Proofs of homomesy often lead one to develop tools that further our understanding of the underlying dynamics, e.g., by finding an equivariant bijection. These notions can be lifted to higher (piecewiselinear and birational) realms, of which the combinatorial situation is a discrete shadow, and the resulting identities are somewhat surprising. Maps that can be decomposed as products of ``toggling'' involutions are particularly amenable to this line of analysis.
This talk will be a introduction to these ideas, giving a number of examples.

27018

Wednesday 2/24 3:00 PM

Sarah Mason, Wake Forest University

Quasisymmetric Macdonald polynomials
 Sarah Mason, Wake Forest University
 Quasisymmetric Macdonald polynomials
 02/24/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
We introduce a quasisymmetric analogue of Macdonald polynomials, originating from work by Corteel, Mandelshtam, and Williams on multiline queues. Along the way we produce a new and compactified combinatorial formula for Macdonald polynomials. This is joint work with Corteel, Haglund, Mandelshtam, and Williams.

27027

Wednesday 3/10 3:00 PM

Bridget Tenner, DePaul University

Odd diagram classes of permutations
 Bridget Tenner, DePaul University
 Odd diagram classes of permutations
 03/10/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
Recently, Brenti and Carnevale introduced an odd analogue of the classical permutation diagram. This gives rise to odd analogues of other permutation aspects such as length and inversions. Unlike in the classical setting, multiple permutations might have the same odd diagram. This prompts the study of "odd diagram classes": sets of permutations having the same odd diagram. We will discuss the rich combinatorial structure of these classes, including connections to pattern avoiding permutations and the Bruhat order.
This is joint work with Francesco Brenti and Angela Carnevale.

28037

Wednesday 3/17 3:00 PM

Stephanie van Willigenburg, University of British Columbia

The epositivity of chromatic symmetric functions
 Stephanie van Willigenburg, University of British Columbia
 The epositivity of chromatic symmetric functions
 03/17/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
The chromatic polynomial was generalized to the chromatic symmetric function by Stanley in his seminal 1995 paper. This function is currently experiencing a flourishing renaissance, in particular the study of the positivity of chromatic symmetric functions when expanded into the basis of elementary symmetric functions, that is, epositivity.
In this talk we approach the question of epositivity from various angles. Most pertinently we resolve the 1995 statement of Stanley that no known graph exists that is not contractible to the claw, and whose chromatic symmetric function is not epositive.
This is joint work with Soojin Cho, Samantha Dahlberg, Angele Foley and Adrian She, and no prior knowledge is assumed.

29045

Wednesday 3/24 3:00 PM

Jo EllisMonaghan, Kortewegde Vries Instituut voor Wiskunde, Universiteit van Amsterdam

Graph theoretical tools for DNA selfassembly
 Jo EllisMonaghan, Kortewegde Vries Instituut voor Wiskunde, Universiteit van Amsterdam
 Graph theoretical tools for DNA selfassembly
 03/24/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
Applications of immediate concern have driven some of the most interesting questions in the field of graph theory, for example graph drawing and computer chip layout problems, random graph theory and modeling the internet, graph connectivity measures and ecological systems, etc. Currently, scientists are engineering selfassembling DNA molecules to serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis. Often, the selfassembled objects, e.g. lattices or polyhedral skeletons, may be modeled as graphs. Thus, these new technologies in selfassembly are now generating challenging new design problems for which graph theory is a natural tool. We will present some new applications in DNA selfassembly and describe some of the graphtheoretical design strategy problems arising from them. We will see how finding optimal design strategies leads to developing new algorithms for graphs, addressing new computational complexity questions, and finding new graph invariants corresponding to the minimum number of components necessary to build a target structure under various laboratory settings.

29047

Wednesday 3/31 3:00 PM

Ira Gessel, Brandeis University

Counting graphs with neighborhood restrictions
 Ira Gessel, Brandeis University
 Counting graphs with neighborhood restrictions
 03/31/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
A graph is called pointdetermining (or mating type) if no two vertices have the same neighborhood. An arbitrary graph can be reduced to a pointdetermining graph by contracting each set of vertices with the same neighborhood to a single vertex, and this decomposition enables us to give a simple exponential generating function for counting pointdetermining graphs, as accomplished by Ronald Read in 1989. In this talk we will discuss a closely related problem: counting graphs in which no two vertices have complementary neighborhoods. The decomposition approach does not work here. Instead we apply inclusionexclusion, similarly to its use in rook theory, to obtain a simple exponential generating function for these graphs. We also discuss how this application of inclusionexclusion is related to Möbius inversion, and how it can be applied to some related problems.

29060

Wednesday 4/7 3:00 PM

Volker Strehl, FriedrichAlexanderUniversität

A valuation problem for strict partitions — and where it comes from
 Volker Strehl, FriedrichAlexanderUniversität
 A valuation problem for strict partitions — and where it comes from
 04/07/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
I will present a rational function valuation on strict partitions as shapes
that is defined via shifted standard tableaux. The goal is to determine
explicit expressions for this valuation by solving a linear system that
reflects the lattice structure of strict partitions.
Somewhat surprisingly, this leads into the area of symmetric functions.
The problem as such may appear as an isolated curiosity, yet is motivated
by the extension of the model for an asymmetric annihilation process originally proposed by A. Ayyer and K. Mallick (2010).

29062

Wednesday 4/14 3:00 PM

Sara Billey, University of Washington

Existence and hardness of conveyor belts
 Sara Billey, University of Washington
 Existence and hardness of conveyor belts
 04/14/2021
 3:00 PM  3:50 PM
 Online (virtual meeting)
(Virtual Meeting Link)
 Bruce E Sagan (bsagan@msu.edu)
We will present the notion of a conveyor belt configuration on disjoint disks in the plane, which means a tight simple closed curve that touches the boundary of each disk. An open problem of Manuel Abellanas asks whether every set of disjoint closed unit disks in the plane can be connected by a conveyor belt, possibly touched multiple times. We will present three main results. 1) For unit disks whose centers are both xmonotone and ymonotone, or whose centers have xcoordinates that differ by at least two units, a conveyor belt always exists and can be found efficiently. 2) It is NPcomplete to determine whether disks of arbitrary radii have a conveyor belt, and it remains NPcomplete when we constrain the belt to touch disks exactly once. 3) Any disjoint set of n disks of arbitrary radii can be augmented by O(n) “guide” disks so that the augmented system has a conveyor belt touching each disk exactly once, answering a conjecture of Demaine, Demaine, and Palop. Many open problems remain on this topic and we will share some of our favorites. This talk is based on joint work with Molly Baird, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, and Joshua P. Swanson.
