An official website of the United States government
Abstract A barcode is a finite multiset of intervals on the real line. Jaramillo-Rodriguez (2023) previously defined a map from the space of barcodes with a fixed number of bars to a set of multipermutations, which presented new combinatorial invariants on the space of barcodes. A partial order can be defined on these multipermutations, resulting in a class of posets known as combinatorial barcode lattices. In this paper, we provide a number of equivalent definitions for the combinatorial barcode lattice, show that its Möbius function is a restriction of the Möbius function of the symmetric group under the weak Bruhat order, and show its ground set is the Jordan-Hölder set of a labeled poset. Furthermore, we obtain formulas for the number of join-irreducible elements, the rank-generating function, and the number of maximal chains of combinatorial barcode lattices. Lastly, we make connections between intervals in the combinatorial barcode lattice and certain classes of matchings.
more »
« less
Shellability of face posets of electrical networks and the CW poset property
We prove a conjecture of Thomas Lam that the face posets of stratified spaces of planar resistor networks are shellable. These posets are called uncrossing partial orders. This shellability result combines with Lam's previous result that these same posets are Eulerian to imply that they are CW posets, namely that they are face posets of regular CW complexes. Certain subposets of uncrossing partial orders are shown to be isomorphic to type A Bruhat order intervals; our shelling is shown to coincide on these intervals with a Bruhat order shelling which was constructed by Matthew Dyer using a reflection order. Our shelling for uncrossing posets also yields an explicit shelling for each interval in the face posets of the edge product spaces of phylogenetic trees, namely in the Tuffley posets, by virtue of each interval in a Tuffley poset being isomorphic to an interval in an uncrossing poset. This yields a more explicit proof of the result of Gill, Linusson, Moulton and Steel that the CW decomposition of Moulton and Steel for the edge product space of phylogenetic trees is a regular CW decomposition.
more »
« less
- Award ID(s):
- 1953931
- PAR ID:
- 10229732
- Date Published:
- Journal Name:
- Advances in applied mathematics
- Volume:
- 127
- ISSN:
- 0196-8858
- Page Range / eLocation ID:
- 1--37
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper is the third in a series of manuscripts that examine the combinatorics of the Kunz polyhedron $$P_m$$, whose positive integer points are in bijection with numerical semigroups (cofinite subsemigroups of $$\mathbb Z_{\ge 0}$$) whose smallest positive element is $$m$$. The faces of $$P_m$$ are indexed by a family of finite posets (called Kunz posets) obtained from the divisibility posets of the numerical semigroups lying on a given face. In this paper, we characterize to what extent the minimal presentation of a numerical semigroup can be recovered from its Kunz poset. In doing so, we prove that all numerical semigroups lying on the interior of a given face of $$P_m$$ have identical minimal presentation cardinality, and we provide a combinatorial method of obtaining the dimension of a face from its corresponding Kunz poset.more » « less
-
The set of equivalence classes of cobounded actions of a group on different hyperbolic metric spaces carries a natural partial order. The resulting poset thus gives rise to a notion of the “best” hyperbolic action of a group as the largest element of this poset, if such an element exists. We call such an action a largest hyperbolic action. While hyperbolic groups admit the largest hyperbolic actions, we give evidence in this paper that this phenomenon is rare for non-hyperbolic groups. In particular, we prove that many families of groups of geometric origin do not have the largest hyperbolic actions, including for instance many 3-manifold groups and most mapping class groups. Our proofs use the quasi-trees of metric spaces of Bestvina–Bromberg–Fujiwara, among other tools. In addition, we give a complete characterization of the poset of hyperbolic actions of Anosov mapping torus groups, and we show that mapping class groups of closed surfaces of genus at least two have hyperbolic actions which are comparable only to the trivial action.more » « less
-
The Wiener index of a finite graph $$G$$ is the sum over all pairs $(p,q)$ of vertices of $$G$$ of the distance between $$p$$ and $$q$$. When $$P$$ is a finite poset, we define its Wiener index as the Wiener index of the graph of its Hasse diagram. In this paper, we find exact expressions for the Wiener indices of the distributive lattices of order ideals in minuscule posets. For infinite families of such posets, we also provide results on the asymptotic distribution of the distance between two random order ideals.more » « less
-
null (Ed.)Abstract The $$(P, \omega )$$-partition generating function of a labeled poset $$(P, \omega )$$ is a quasisymmetric function enumerating certain order-preserving maps from $$P$$ to $${\mathbb{Z}}^+$$. We study the expansion of this generating function in the recently introduced type 1 quasisymmetric power sum basis $$\{\psi _{\alpha }\}$$. Using this expansion, we show that connected, naturally labeled posets have irreducible $$P$$-partition generating functions. We also show that series-parallel posets are uniquely determined by their partition generating functions. We conclude by giving a combinatorial interpretation for the coefficients of the $$\psi _{\alpha }$$-expansion of the $$(P, \omega )$$-partition generating function akin to the Murnaghan–Nakayama rule.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/https://doi.org/10.1016/j.aam.2021.102178
