We construct nonconstructible simplicial d-spheres with d + 10 vertices and nonconstructible, nonrealizable simplicial d-balls with d + 9 vertices for $d\geq 3$.
The construction of the Bier sphere \textrm{Bier}(K) for a simplicial complex K is due to Bier (1992). Björner, Paffenholz, Sjöstrand and Ziegler (2005) generalize this construction to obtain a Bier ...poset \textrm{Bier}(P,I) from any bounded poset P and any proper ideal I\subseteq P. They show shellability of \textrm{Bier}(P,I) for the case P=B_n, the boolean lattice, and thereby obtain `many shellable spheres' in the sense of Kalai (1988). We put the Bier construction into the general framework of the theory of nested set complexes of Feichtner and Kozlov (2004). We obtain `more shellable spheres' by proving the general statement that combinatorial blowups, hence stellar subdivisions, preserve shellability.
Recently in Koshevoy (Math. Social Sci. 38 (1999) 35), it was established a connection between the theory of choice functions satisfying path-independence condition and closure operators with the ...anti-exchange property. Closure operators with the anti-exchange property are a combinatorial abstraction of usual convex hull closure in Euclidean spaces. Interest in these structures has its sources in different fields of mathematics. We demonstrate that path-independent choice functions provide another source for this structure. Specifically, we associate to a choice function
f a collection of expanding maps. We prove that a function
f is path-independent if and only if all the maps of this collection are coinciding anti-exchange closure operators. Consequences of such a characterization are demonstrated.
Constructibility is a combinatorial property of simplicial complexes. In general, it requires a great deal of time to decide whether a simplicial complex is constructible or not. In this paper, we ...consider sufficient conditions for nonconstructibility of simplicial 3-balls to investigate efficient algorithms for the decision problem.
The absolute order on the hyperoctahedral group Kallipoliti, Myrto
Discrete Mathematics and Theoretical Computer Science,
01/2009, Volume:
DMTCS Proceedings vol. AK,..., Issue:
Proceedings
Journal Article, Conference Proceeding
Peer reviewed
Open access
The absolute order on the hyperoctahedral group $B_n$ is investigated. It is shown that every closed interval in this order is shellable, those closed intervals which are lattices are characterized ...and their zeta polynomials are computed. Moreover, using the notion of strong constructibility, it is proved that the order ideal generated by the Coxeter elements of $B_n$ is homotopy Cohen-Macaulay and the Euler characteristic of the order complex of the proper part of this ideal is computed. Finally, an example of a non Cohen-Macaulay closed interval in the absolute order on the group $D_4$ is given and the closed intervals of $D_n$ which are lattices are characterized.
Nous étudions l'ordre absolu sur le groupe hyperoctahédral $B_n$. Nous montrons que chaque intervalle fermé de cet ordre est shellable, caractérisons les treillis parmi ces intervalles et calculons les polynômes zêta de ces derniers. De plus, en utilisant la notion de constructibilité forte, nous prouvons que l'idéal engendré par les éléments de Coxeter de $B_n$ est Cohen-Macaulay pour l'homotopie, et nous calculons la caractéristique d'Euler du complexe associé à cet idéal. Pour finir, nous exhibons un exemple d'intervalle fermé non Cohen-Macaulay dans l'ordre absolu du groupe $D_4$, et caractérisons les intervalles fermés de $D_n$ qui sont des treillis.
Tree-Shellability of Restricted DNFs TAKENAGA, Yasuhiko; KATOUGI, Nao
IEICE Transactions on Information and Systems,
2008, Volume:
E91.D, Issue:
4
Journal Article
Peer reviewed
Open access
A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime ...implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.
In this paper, we treat the problem to find an efficient algorithm to decide constructibility. Such an algorithm was given only under the condition that the given simplicial complex is a triangulated ...3-ball with all the vertices on the boundary M. Hachimori, Non-constructible simplicial balls and a way of testing constructibility, Discrete Comput. Geom. 22 (1999) 223–230. Here we extend this result to the case that the triangulated 3-ball has at most two interior vertices. Our algorithm runs in O(#facets) time. Also, we give an example which shows that the same strategy cannot be used for the cases with more than two interior vertices.
There is currently no efficient algorithm for deciding whether a given simplicial complex is shellable. We propose a practical method that decides shellability of simplicial complexes based on ...reverse search, which improves an earlier attempt by Moriyama, Nagai and Imai. We also propose to use Macaulay's theorem during the search. This works efficiently in high-dimensional cases.
Some posets of binary leaf-labeled trees are shown to be supersolvable lattices and explicit EL-labelings are given. Their characteristic polynomials are computed, recovering their known ...factorization in a different way.
PDF
