Fertilitopes

DOI10.1007/S00454-023-00488-YMaRDI QIDQ6050220zbMATH OpenOpenAlexFDO

Authors Colin Defant

Publication date 12 October 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.11836

zbMATH Keywords

cumulantsdiscrete polymatroidfertilitopenestohedronquasicanonical treestack-sorting

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19) Noncommutative probability and statistics (46L53) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: We introduce tools from discrete convexity theory and polyhedral geometry into the theory of West's stack-sorting map $s$. Associated to each permutation $pi$ is a particular set $mathcalV(pi)$ of integer compositions that appears in a formula for the fertility of $pi$, which is defined to be $|s^{-1}(pi)|$. These compositions also feature prominently in more general formulas involving families of colored binary plane trees called troupes and in a formula that converts from free to classical cumulants in noncommutative probability theory. We show that $mathcalV(pi)$ is a transversal discrete polymatroid when it is nonempty. We define the fertilitope of $pi$ to be the convex hull of $mathcalV(pi)$, and we prove a surprisingly simple characterization of fertilitopes as nestohedra arising from full binary plane trees. Using known facts about nestohedra, we provide a procedure for describing the structure of the fertilitope of $pi$ directly from $pi$ using Bousquet-M'elou's notion of the canonical tree of $pi$. As a byproduct, we obtain a new combinatorial cumulant conversion formula in terms of generalizations of canonical trees that we call quasicanonical trees. We also apply our results on fertilitopes to study combinatorial properties of the stack-sorting map. In particular, we show that the set of fertility numbers has density $1$, and we determine all infertility numbers of size at most $126$. Finally, we reformulate the conjecture that $su{m}_{sigmain{s}^{-1}(pi)}{x}^{extdes(sigma)+1}$ is always real-rooted in terms of nestohedra, and we propose natural ways in which this new version of the conjecture could be extended.

Recommendations

• Fertility numbers
• Troupes, cumulants, and stack-sorting
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Fertility monotonicity and average complexity of the stack-sorting map
• Troupes, cumulants, and stack-sorting

Cites work

• 312-Avoiding reduced valid hook configurations and duck words
• \(\eta\)-series and a Boolean Bercovici--Pata bijection for bounded \(k\)-tuples
• A survey of stack sortable permutations
• Actions on permutations and unimodality of descent polynomials
• Addition of certain non-commuting random variables
• Alcoved polytopes. I.
• Asymptotics of 3-stack-sortable permutations
• Catalan intervals and uniquely sorted permutations
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Counting faces of nestohedra
• Cumulant-cumulant relations in free probability theory from Magnus' expansion
• Cumulants of the q-semicircular law, Tutte polynomials, and heaps
• Discrete Convex Analysis
• Discrete polymatroids
• Faces of generalized permutohedra
• Fertility monotonicity and average complexity of the stack-sorting map
• Fertility numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Free cumulants and enumeration of connected partitions
• Further bijections to pattern-avoiding valid hook configurations
• scientific article; zbMATH DE number 5729471 (Why is no real title available?)
• scientific article; zbMATH DE number 4002828 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Lattice paths and pattern-avoiding uniquely sorted permutations
• Lectures on the Combinatorics of Free Probability
• Lorentzian polynomials
• Matroid polytopes, nested sets and Bergman fans
• Monotone, free, and Boolean cumulants: a shuffle algebra approach
• Multiplicative functions on the lattice of non-crossing partitions and free convolution
• Nested complexes and their polyhedral realizations
• On linear transformations preserving the Pólya frequency property
• Patterns in permutations and words.
• Permutohedra, Associahedra, and Beyond
• Polyurethane toggles
• Postorder Preimages
• Preimages under the Queuesort algorithm
• Preimages under the stack-sorting algorithm
• Quantifying noninvertibility in discrete dynamical systems
• Relations between cumulants in noncommutative probability
• Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
• Sorted and/or sortable permutations
• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence
• Symmetry and unimodality in \(t\)-stack sortable permutations
• Troupes, cumulants, and stack-sorting
• Unimodality of a refinement of Lassalle's sequence
• Which nestohedra are removahedra?

Cited in

(5)

• Troupes, cumulants, and stack-sorting
• Fertility numbers
• Fertility monotonicity and average complexity of the stack-sorting map
• Celebrating Loday's associahedron
• Interval hypergraphic lattices

This page was built for publication: Fertilitopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6050220)