Talk_id | Date | Speaker | Title |
26940
|
Wednesday 1/20 3:00 PM
|
Sergi Elizalde, Dartmouth College
|
Descents on quasi-Stirling permutations
- Sergi Elizalde, Dartmouth College
- Descents on quasi-Stirling 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 quasi-Stirling permutations, which are in bijection with labeled rooted plane trees. Archer et al. introduced these permutations, and conjectured that there are $(n+1)^{n-1}$ quasi-Stirling permutations of size $n$ having $n$ descents.
In this talk we prove this conjecture. More generally, we give the generating function for quasi-Stirling 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 quasi-Stirling permutations.
Finally, we extend our results to a one-parameter family of permutations, called $k$-quasi-Stirling 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örner-Wachs, 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 Irwin-Hall and normal distributions. In the case of forests, we use graph-theoretic 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}^{n-1} \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 two-parameter 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 "T-paths". Recently, Penner and Zeitlin constructed a super-algebra from a triangulation, and an analogue of the Ptolemy relation in this situation. I will describe a generalization of "T-paths" 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 action-packed introduction to homomesy
- Tom Roby, University of Connecticut
- An action-packed 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 well-behaved 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 (piecewise-linear 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 e-positivity of chromatic symmetric functions
- Stephanie van Willigenburg, University of British Columbia
- The e-positivity 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, e-positivity.
In this talk we approach the question of e-positivity 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 e-positive.
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 Ellis-Monaghan, Korteweg-de Vries Instituut voor Wiskunde, Universiteit van Amsterdam
|
Graph theoretical tools for DNA self-assembly
- Jo Ellis-Monaghan, Korteweg-de Vries Instituut voor Wiskunde, Universiteit van Amsterdam
- Graph theoretical tools for DNA self-assembly
- 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 self-assembling DNA molecules to serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis. Often, the self-assembled objects, e.g. lattices or polyhedral skeletons, may be modeled as graphs. Thus, these new technologies in self-assembly are now generating challenging new design problems for which graph theory is a natural tool. We will present some new applications in DNA self-assembly and describe some of the graph-theoretical 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 point-determining (or mating type) if no two vertices have the same neighborhood. An arbitrary graph can be reduced to a point-determining 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 point-determining 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 inclusion-exclusion, similarly to its use in rook theory, to obtain a simple exponential generating function for these graphs. We also discuss how this application of inclusion-exclusion 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, Friedrich-Alexander-Universität
|
A valuation problem for strict partitions — and where it comes from
- Volker Strehl, Friedrich-Alexander-Universitä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 x-monotone and y-monotone, or whose centers have x-coordinates that differ by at least two units, a conveyor belt always exists and can be found efficiently. 2) It is NP-complete to determine whether disks of arbitrary radii have a conveyor belt, and it remains NP-complete 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.
|