Trees with labelled leaves and with all other vertices of degree three play an important role in systematic biology and other areas of classification. A classical combinatorial result ensures that ...such trees can be uniquely reconstructed from the distances between the leaves (when the edges are given any strictly positive lengths). Moreover, a linear number of these pairwise distance values suffices to determine both the tree and its edge lengths. A natural set of pairs of leaves is provided by any ‘triplet cover’ of the tree (based on the fact that each non-leaf vertex is the median vertex of three leaves). In this paper we describe a number of new results concerning triplet covers of minimum size. In particular, we characterize such covers in terms of an associated graph being a 2-tree. Also, we show that minimum triplet covers are ‘shellable’ and thereby provide a set of pairs for which the inter-leaf distance values will uniquely determine the underlying tree and its associated branch lengths.
We prove a new theorem of Tverberg–van Kampen–Flores type, which confirms a conjecture of Blagojević et al. about the existence of ‘balanced Tverberg partitions’ (Conjecture 6.6 in Tverberg plus ...constraints, Bull. London Math. Soc. 46:953–967 (
2014
). The conditions in this theorem are somewhat weaker than in the original conjecture, and we show that the theorem is optimal in the sense that the new (weakened) condition is also necessary. Among the consequences is a positive answer (Theorem
7.2
) to the ‘balanced case’ of the question asking whether each
admissible
r
-tuple is
Tverberg prescribable
(Blagojević et al.
2014
, Question 6.9).
In a seminal 1994 paper Lusztig (1994)
26, Lusztig extended the theory of total positivity by introducing the totally non-negative part
(
G
/
P
)
⩾
0
of an arbitrary (generalized, partial) flag ...variety
G
/
P
. He referred to this space as a “remarkable polyhedral subspace”, and conjectured a decomposition into cells, which was subsequently proven by the first author Rietsch (1998)
33. In Williams (2007)
40 the second author made the concrete conjecture that this cell decomposed space is the next best thing to a polyhedron, by conjecturing it to be a
regular CW complex that is homeomorphic to a closed ball. In this article we use discrete Morse theory to prove this conjecture up to homotopy-equivalence. Explicitly, we prove that the boundaries of the cells are homotopic to spheres, and the closures of cells are contractible. The latter part generalizes a result of Lusztig's (1998)
28, that
(
G
/
P
)
⩾
0
– the closure of the top-dimensional cell – is contractible. Concerning our result on the boundaries of cells, even the special case that the boundary of the top-dimensional cell
(
G
/
P
)
>
0
is homotopic to a sphere, is new for all
G
/
P
other than projective space.
Ideals with linear quotients Jahan, Ali Soleyman; Zheng, Xinxian
Journal of combinatorial theory. Series A,
2010, 2010-01-00, Volume:
117, Issue:
1
Journal Article
Peer reviewed
Open access
We study basic properties of monomial ideals with linear quotients. It is shown that if the monomial ideal
I has linear quotients, then the squarefree part of
I and each component of
I as well as
m
I
...have linear quotients, where
m
is the graded maximal ideal of the polynomial ring. As an analogy to the Rearrangement Lemma of Björner and Wachs we also show that for a monomial ideal with linear quotients the admissible order of the generators can be chosen degree increasingly.
Recently, methods have been proposed to reconstruct a 2-manifold surface from a sparse cloud of points estimated from an image sequence. Once a 3D Delaunay triangulation is computed from the points, ...the surface is searched by growing a set of tetrahedra whose boundary is maintained 2-manifold. Shelling is a step that adds one tetrahedron at once to the growing set. This paper surveys properties that helps to understand the shelling performances: shelling provides most tetrahedra enclosed by the final surface, but it can “get stuck” or block in unexpected cases.
Geometric lattices are characterized in this paper as those finite, atomic lattices such that every atom ordering induces a lexicographic shelling given by an edge labeling known as a minimal ...labeling. Equivalently, geometric lattices are shown to be exactly those finite lattices such that every ordering on the join-irreducibles induces a lexicographic shelling. This new characterization fits into a similar paradigm as McNamaraʼs characterization of supersolvable lattices as those lattices admitting a different type of lexicographic shelling, namely one in which each maximal chain is labeled with a permutation of {1,…,n}.
If a d-dimensional pure simplicial complex C has a shelling, which is a specific total order of all facets of C, C is said to be shellable. We consider the problem of deciding whether C is shellable ...or not. This problem is solved in linear time of m, the number of all facets of C, if d=1 or C is a pseudomanifold in d=2. Otherwise it is unknown at this point whether the decision of shellability can be solved in polynomial time of m. Thus, for the latter case, we had no choice but to apply a brute force method to the decision problem; namely checking up to the m! ways to see if one can arrange all the m facets of C into a shelling. In this paper, we introduce a new concept, called h-assignment, to C and propose a practical method using h-assignments to decide whether C is shellable or not. Our method can make the decision of shellability of C by smaller sized computation than the brute force method.
PDF
