We introduce random discrete Morse theory as a computational scheme to measure the complexity of a triangulation. The idea is to try to quantify the frequency of discrete Morse matchings with few ...critical cells. Our measure will depend on the topology of the space, but also on how nicely the space is triangulated. The scheme we propose looks for optimal discrete Morse functions with an elementary random heuristic. Despite its naiveté, this approach turns out to be very successful even in the case of huge inputs. In our view, the existing libraries of examples in computational topology are "too easy" for testing algorithms based on discrete Morse theory. We propose a new library containing more complicated (and thus more meaningful) test examples.
In the computation of the intersection cohomology of Shimura varieties, or of the L 2 cohomology of equal rank locally symmetric spaces, combinatorial identities involving averaged discrete series ...characters of real reductive groups play a large technical role. These identities can become very complicated and are not always well-understood (see for example the appendix of 8). We propose a geometric approach to these identities in the case of Siegel modular varieties using the combinatorial properties of the Coxeter complex of the symmetric group. Apart from some introductory remarks about the origin of the identities, our paper is entirely combinatorial and does not require any knowledge of Shimura varieties or of representation theory.
We construct the first explicit example of a simplicial 3-ball $B_{15,66}$ that is not collapsible. It has only 15 vertices. We exhibit a second 3-ball $B_{12,38}$ with 12 vertices that is ...collapsible and not shellable, but evasive. Finally, we present the first explicit triangulation of a 3-sphere $S_{18, 125}$ (with only 18 vertices) that is not locally constructible. All these examples are based on knotted subcomplexes with only three edges; the knots are the trefoil, the double trefoil, and the triple trefoil, respectively. The more complicated the knot is, the more distant the triangulation is from being polytopal, collapsible, etc. Further consequences of our work are:(1) Unshellable 3-spheres may have vertex-decomposable barycentric subdivisions. (This shows the strictness of an implication proven by Billera and Provan.)(2) For $d$-balls, vertex-decomposable implies non-evasive implies collapsible, and for $d=3$ all implications are strict. (This answers a question by Barmak.)(3) Locally constructible 3-balls may contain a double trefoil knot as a 3-edge subcomplex. (This improves a result of Benedetti and Ziegler.)(4) Rudin's ball is non-evasive.
We consider three notions of connectivity and their interactions in partially ordered sets coming from reduced factorizations of an element in a generated group. While one form of connectivity ...essentially reflects the connectivity of the poset diagram, the other two are a bit more involved: Hurwitz-connectivity has its origins in algebraic geometry, and shellability in topology. We propose a framework to study these connectivity properties in a uniform way. Our main tool is a certain linear order of the generators that is compatible with the chosen element.
Quasi-triangulations of a non-orientable surface were introduced by Dupont and Palesi (J Algebr Comb 42(2):429–472,
2015
). The quasi-arc complex provides an intricate description of the ...combinatorics of these quasi-triangulations. This is the simplicial complex where vertices correspond to quasi-arcs and maximal simplices to quasi-triangulations. We prove that when the quasi-arc complex is finite then it is shellable and, as a consequence, it is homeomorphic to a sphere.
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).
PDF
