The set of all permutations, ordered by pattern containment, is a poset. We present an order isomorphism from the poset of permutations with a fixed number of descents to a certain poset of words ...with subword order. We use this bijection to show that intervals of permutations with a fixed number of descents are shellable, and we present a formula for the Möbius function of these intervals. We present an alternative proof for a result on the Möbius function of intervals 1,π such that π has exactly one descent. We prove that if π has exactly one descent and avoids 456123 and 356124, then the intervals 1,π have no nontrivial disconnected subintervals; we conjecture that these intervals are shellable.
In this paper, we introduce four kinds of strengthenings of partitionability of simplicial complexes, all of which are satisfied by the partitioning induced by shellability. We show the relations of ...these different strengthenings of partitionability.
We consider a
q
-analogue of abstract simplicial complexes, called
q
-complexes, and discuss the notion of shellability for such complexes. It is shown that
q
-complexes formed by independent ...subspaces of a
q
-matroid are shellable. Further, we explicitly determine the homology of
q
-complexes corresponding to uniform
q
-matroids. We also outline some partial results concerning the determination of homology of arbitrary shellable
q
-complexes.
In this manuscript we study inclusion posets of Borel orbit closures on (symmetric) matrices. In particular, we show that the Bruhat poset of partial involutions is a lexicographically shellable ...poset. We determine which subintervals of the Bruhat posets are Eulerian, and moreover, by studying certain embeddings of the symmetric groups and their involutions into rook matrices and partial involutions, respectively, we obtain new shelling orders on the corresponding order complexes.
Given a triangulation of a point set in the plane, a
flip
deletes an edge
e
whose removal leaves a convex quadrilateral, and replaces
e
by the opposite diagonal of the quadrilateral. It is well known ...that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label
l
, if edge
e
has label
l
in the first triangulation and edge
f
has label
l
in the second triangulation, then there must be some sequence of flips that moves label
l
from
e
to
f
, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the
Orbit Conjecture
, which states that this necessary condition is also sufficient, i.e. that
all
labels can be simultaneously mapped to their destination if and only if
each
label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with
O
(
n
8
)
being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of
O
(
n
7
)
on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the
flip complex
, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
This article is concerned with the constants that appear in Harish-Chandra's character formula for stable discrete series of real reductive groups, although it does not require any knowledge about ...real reductive groups or discrete series. In Harish-Chandra's work the only information we have about these constants is that they are uniquely determined by an inductive property. Later Goresky--Kottwitz--MacPherson and Herb gave different formulas for these constants. In this article we generalize these formulas to the case of arbitrary finite Coxeter groups (in this setting, discrete series no longer make sense), and give a direct proof that the two formulas agree. We actually prove a slightly more general identity that also implies the combinatorial identity underlying the discrete series character identities of Morel. We deduce this identity from a general abstract theorem giving a way to calculate the alternating sum of the values of a valuation on the chambers of a Coxeter arrangement. We also introduce a ring structure on the set of valuations on polyhedral cones in Euclidean space with values in a fixed ring. This gives a theoretical framework for the valuation appearing in Appendix A of the Goresky--Kottwitz--MacPherson paper. In Appendix B we extend the notion of 2-structures (due to Herb) to pseudo-root systems.
Shellability is NP-complete Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana ...
Journal of the ACM,
06/2019, Volume:
66, Issue:
3
Journal Article
Peer reviewed
Open access
We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. ...Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.
Let G be a finite simple graph. The line graph L (G) represents adjacencies between edges of G. We define first line simplicial complex ΔL (G) of G containing Gallai and anti-Gallai simplicial ...complexes ΔΓ (G) and ΔΓ′ (G) (respectively) as spanning subcomplexes. We establish the relation between Euler characteristics of line and Gallai simplicial complexes. We prove that the shellability of a line simplicial complex does not hold in general. We give formula for Euler characteristic of line simplicial complex associated to Jahangir graph Jm,n by presenting an algorithm.
It is a classical result that an unrooted tree T having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. ...Moreover, if each non-leaf vertex of T has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in T is the following: for each non-leaf vertex v, choose a leaf in each of the three components of T−v, group these three leaves into three pairs, and take the union of this set over all choices of v. This forms a so-called ‘triplet cover’ for T. In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for T uniquely determine T and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, ‘sparse’, and ‘shellable’.
•We settle a conjecture concerning triplet covers in J. Math. Biol., 2012, 65:77.•We characterize minimal triplet covers in terms of 2-tree decompositions•We provide an example of a non-shellable triplet cover.
PDF
