12 pages, 3 figures
Let $I_n$ be the set of involutions in the symmetric group $S_n$, and for $A \subseteq \{0,1,\ldots,n\}$, let \ F_n^A=\{\sigma \in I_n \mid \text{$\sigma$ has $a$ fixed points for ...some $a \in A$}\}. \ We give a complete characterisation of the sets $A$ for which $F_n^A$, with the order induced by the Bruhat order on $S_n$, is a graded poset. In particular, we prove that $F_n^{\{1\}}$ (i.e., the set of involutions with exactly one fixed point) is graded, which settles a conjecture of Hultman in the affirmative. When $F_n^A$ is graded, we give its rank function. We also give a short new proof of the EL-shellability of $F_n^{\{0\}}$ (i.e., the set of fixed point-free involutions), which was recently proved by Can, Cherniavsky, and Twelbeck.
Soit $I_n$ l’ensemble d’involutions dans le groupe symétrique $S_n$, et pour $A \subseteq \{0,1,\ldots,n\}$, soit\ F_n^A=\{\sigma \in I_n \mid \text{$\sigma$ a $a$ points fixes pour quelque $a \in A$}\}. \ Nous caractérisons tous les ensembles $A$ dont les $F_n^A$ , avec l’ordre induit par l’ordre de Bruhat sur $S_n$, est un posetgradué. En particulier, nous démontrons que $F_n^{\{1\}}$ (c’est-à-dire, l’ensemble d’involutions avec précis en point fixe)est gradué, ce qui résout une conjecture d’Hultman à l’affirmative. Lorsque $F_n^A$ est gradué, nous donnons sa fonctionde rang. En plus, nous donnons une nouvelle démonstration courte l’EL-shellability de $F_n^{\{0\}}$ (c’est-à-dire, l’ensembled’involutions sans points fixes), établie récemment par Can, Cherniavsky et Twelbeck.
A polytopal digraph G(P) is an orientation of the skeleton of a convex polytope P. The possible non-degenerate pivot operations of the simplex method in solving a linear program over P can be ...represented as a special polytopal digraph known as an LP digraph. Presently there is no general characterization of which polytopal digraphs are LP digraphs, although four necessary properties are known: acyclicity, unique sink orientation (USO), the Holt–Klee property and the shelling property. The shelling property was introduced by Avis and Moriyama (2009), where two examples are given in d=4 dimensions of polytopal digraphs satisfying the first three properties but not the shelling property. The smaller of these examples has n=7 vertices. Avis, Miyata and Moriyama (2009) constructed for each d⩾4 and n⩾d+2, a d-polytope P with n vertices which has a polytopal digraph which is an acyclic USO that satisfies the Holt–Klee property, but does not satisfy the shelling property. The construction was based on a minimal such example, which has d=4 and n=6. In this paper we explore the shelling condition further. First we give an apparently stronger definition of the shelling property, which we then prove is equivalent to the original definition. Using this stronger condition we are able to give a more general construction of such families. In particular, we show that given any 4-dimensional polytope P with n0 vertices whose unique sink is simple, we can extend P for any d⩾4 and n⩾n0+d−4 to a d-polytope with these properties that has n vertices. Finally we investigate the strength of the shelling condition for d-crosspolytopes, for which Develin (2004) has given a complete characterization of LP orientations.
We give new examples of shellable, but not extendably shellable two-dimensional simplicial complexes. They include minimal examples that are smaller than those previously known. We also give new ...examples of shellable, but not vertex decomposable two-dimensional simplicial complexes, including extendably shellable ones. This shows that neither extendable shellability nor vertex decomposability implies the other. We found these examples by enumerating shellable two-dimensional simplicial complexes that are not pseudomanifolds.
In their work on ‘Coxeter-like complexes’, Babson and Reiner introduced a simplicial complex
Δ
T
associated to each tree
T on
n nodes, generalizing chessboard complexes and type A Coxeter complexes. ...They conjectured that
Δ
T
is
(
n
−
b
−
1
)
-connected when the tree has
b leaves. We provide a shelling for the
(
n
−
b
)
-skeleton of
Δ
T
, thereby proving this conjecture. In the process, we introduce notions of weak order and inversion functions on the labellings of a tree
T which imply shellability of
Δ
T
, and we construct such inversion functions for a large enough class of trees to deduce the aforementioned conjecture and also recover the shellability of chessboard complexes
M
m
,
n
with
n
⩾
2
m
−
1
. We also prove that the existence or nonexistence of an inversion function for a fixed tree governs which networks with a tree structure admit greedy sorting algorithms by inversion elimination and provide an inversion function for trees where each vertex has capacity at least its degree minus one.
On Bruhat posets associated to compositions Can, Mahir Bilen; Cherniavsky, Yonah
Discrete Mathematics and Theoretical Computer Science,
01/2014, Volume:
DMTCS Proceedings vol. AT,..., Issue:
Proceedings
Journal Article, Conference Proceeding
Peer reviewed
Open access
The purpose of this work is to initiate a combinatorial study of the Bruhat-Chevalley ordering on certain sets of permutations obtained by omitting the parentheses from their standard cyclic ...notation. In particular, we show that these sets form bounded, graded, unimodal, rank-symmetric and EL-shellable posets. Moreover, we determine the homotopy types of the associated order complexes.
Le but de ce travail est de lancer une étude combinatoire de l’ordre de Bruhat-Chevalley sur certains ensembles de permutations obtenues en omettant les parenthèses de leur notation cyclique standard. En particulier, nous montrons que ces ensembles forment des posets bornés, classés, unimodaux, rang-symétriques et EL-shellable. De plus, nous déterminons les types de complexes d’ordre associés d’homotopie.
The question of shellability of complexes of directed trees was asked by R. Stanley. D. Kozlov showed that the existence of a complete source in a directed graph provides a shelling of its complex of ...directed trees. We will show that this property gives a shelling that is straightforward in some sense. Among the simplicial polytopes, only the crosspolytopes allow such a shelling. Furthermore, we show that the complex of directed trees of a complete double directed graph is a union of suitable spheres. We prove that the complex of directed trees of a directed graph which is essentially a tree is vertex-decomposable. For these complexes we describe their sets of generating facets.
On the Topology of the Cambrian Semilattices Kallipoliti, Myrto; Mühle, Henri
Discrete Mathematics and Theoretical Computer Science,
01/2013, Volume:
DMTCS Proceedings vol. AS,..., Issue:
Proceedings
Journal Article, Conference Proceeding
Peer reviewed
Open access
For an arbitrary Coxeter group $W$, David Speyer and Nathan Reading defined Cambrian semilattices $C_{\gamma}$ as certain sub-semilattices of the weak order on $W$. In this article, we define an ...edge-labelling using the realization of Cambrian semilattices in terms of $\gamma$-sortable elements, and show that this is an EL-labelling for every closed interval of $C_{\gamma}$. In addition, we use our labelling to show that every finite open interval in a Cambrian semilattice is either contractible or spherical, and we characterize the spherical intervals, generalizing a result by Nathan Reading.
Pour tout groupe de Coxeter $W$, David Speyer et Nathan Reading ont défini les demi-treillis Cambriens comme certains sous-demi-treillis de l’ordre faible sur $W$. Dans cet article, nous définissons un étiquetage des arêtes basé sur la réalisation des demi-treillis Cambriens en termes d’éléments$\gamma$-triables, et prouvons que c’est un étiquetage EL pour tout intervalle fermé de $C_{\gamma}$. Nous utilisons de plus cet étiquetage pour ontrer que tout intervalle ouvert fini dans un demi-treillis Cambrien est soit contractile soit sphérique, et nous caractérisons les intervalles sphériques,généralisant ainsi un résultat de Nathan Reading.
For a property
P
of simplicial complexes, a simplicial complex
Γ is an obstruction to
P
if
Γ itself does not satisfy
P
but all of its proper restrictions satisfy
P
. In this paper, we determine all ...obstructions to shellability of dimension ⩽2, refining the previous work by Wachs. As a consequence we obtain that the set of obstructions to shellability, that to partitionability and that to sequential Cohen–Macaulayness all coincide for dimensions ⩽2. We also show that these three sets of obstructions coincide in the class of flag complexes. These results show that the three properties, hereditary-shellability, hereditary-partitionability, and hereditary-sequential Cohen–Macaulayness are equivalent for these classes.
We show that the class of Cohen–Macaulay complexes, that of complexes with constructible subdivisions, and that of complexes with shellable subdivisions differ from each other in every dimension
d
⩾
...2
. Further, we give a characterization of two-dimensional simplicial complexes with shellable subdivisions, and show also that they are constructible.
PDF
