TY - JOUR AB - A graph G=(V, E) is called fully regular if for every independent set I c V, the number of vertices in V\I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph. As an application of our results, we give alternative proofs of two theorems of Stanley and Gao & Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph. As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small. AU - Fang, Lixing AU - Huang, Hao AU - Pach, János AU - Tardos, Gábor AU - Zuo, Junchi ID - 13165 IS - 10 JF - Journal of Combinatorial Theory. Series A SN - 0097-3165 TI - Successive vertex orderings of fully regular graphs VL - 199 ER - TY - JOUR AB - Motivated by recent applications to entropy theory in dynamical systems, we generalise notions introduced by Matthews and define weakly weighted and componentwise weakly weighted (generalised) quasi-metrics. We then systematise and extend to full generality the correspondences between these objects and other structures arising in theoretical computer science and dynamics. In particular, we study the correspondences with weak partial metrics and, if the underlying space is a semilattice, with invariant (generalised) quasi-metrics satisfying the descending path condition, and with strictly monotone semi(-co-)valuations. We conclude discussing, for endomorphisms of generalised quasi-metric semilattices, a generalisation of both the known intrinsic semilattice entropy and the semigroup entropy. AU - Castellano, Ilaria AU - Giordano Bruno, Anna AU - Zava, Nicolò ID - 14362 JF - Theoretical Computer Science SN - 0304-3975 TI - Weakly weighted generalised quasi-metric spaces and semilattices VL - 977 ER - TY - JOUR AB - We characterize critical points of 1-dimensional maps paired in persistent homology geometrically and this way get elementary proofs of theorems about the symmetry of persistence diagrams and the variation of such maps. In particular, we identify branching points and endpoints of networks as the sole source of asymmetry and relate the cycle basis in persistent homology with a version of the stable marriage problem. Our analysis provides the foundations of fast algorithms for maintaining a collection of sorted lists together with its persistence diagram. AU - Biswas, Ranita AU - Cultrera Di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 13182 JF - Journal of Applied and Computational Topology SN - 2367-1726 TI - Geometric characterization of the persistence of 1D maps ER - TY - THES AB - We introduce the notion of a Faustian interchange in a 1-parameter family of smooth functions to generalize the medial axis to critical points of index larger than 0. We construct and implement a general purpose algorithm for approximating such generalized medial axes. AU - Stephenson, Elizabeth R ID - 14226 SN - 2791-4585 TI - Generalizing medial axes with homology switches ER - TY - CONF AB - The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible. AU - Chambers, Erin AU - Fillmore, Christopher D AU - Stephenson, Elizabeth R AU - Wintraecken, Mathijs ED - Goaoc, Xavier ED - Kerber, Michael ID - 11428 SN - 1868-8969 T2 - 38th International Symposium on Computational Geometry TI - A cautionary tale: Burning the medial axis is unstable VL - 224 ER -