This textbook, Counting Rocks!, is the written component of an interactive introduction to combinatorics at the undergraduate level. Throughout the text, we link to videos where we describe the material and provide examples. The major topics in this text are counting problems (Chapters 1-4), proof techniques (Chapter 5), recurrence relations and generating functions (Chapters 6-7), and an introduction to graph theory (Chapters 8-12). The material and the problems we include are standard for an undergraduate combinatorics course. In addition to the linked videos, most chapters contain an investigation section, where students are led through a series of deeper problems on a topic. In several sections, we show students how to use the free, open source computing software SAGE in order to solve problems. We have included many illustrative figures throughout the text, and we end each section and chapter with a list of exercises of varying difficulty.

Let M be a closed Riemannian manifold and let X⊆ M. If the sample X is sufficiently dense relative to the curvature of M, then the Gromov-Hausdorff distance between X and M is bounded from below by half their Hausdorff distance, namely d_GH(X,M) ≥ ½ d_H(X,M). The constant ½ can be improved depending on the dimension and curvature of the manifold M, and obtains the optimal value 1 in the case of the unit circle, meaning that if X⊆ S¹ satisfies d_GH(X,S¹)<π/6, then d_GH(X,S¹)=d_H(X,S¹). We also provide versions lower bounding the Gromov-Hausdorff distance d_GH(X,Y) between two subsets X,Y⊆ M. Our proofs convert discontinuous functions between metric spaces into simplicial maps between Čechech or Vietoris-Rips complexes. We then produce topological obstructions to the existence of certain maps using the nerve lemma and the fundamental class of the manifold.

Consider a mobile sensor network, in which each sensor covers a ball. Sensors do not know their locations, but can detect if the covered balls overlap. An intruder cannot pass undetected between overlapping sensors. An evasion path exists if it is possible for an intruder to move in the domain without ever entering a covered region. We examine two time-varying topological spaces arising from such mobile sensor networks. These examples were constructed by Adams and Carlsson to show that the time-varying homotopy type of the covered region does not determine whether an evasion path exists or not. One of these spaces has an evasion path and the other does not, which means that the uncovered regions are not time-varying homotopy equivalent. We show that the covered regions of these spaces are not time-varying homeomorphic, even though they are time-varying homotopy equivalent. We then elaborate on this time-varying homotopy equivalence between the covered regions.

In this paper, we study the basic properties of persistent homotopy groups. We show that the persistent fundamental group benefits from the Van Kampen theorem, and the interleaving distance between total spaces is less than or equal to the maximum of the interleaving distances between subspaces. We also prove excision and Hurewicz theorems for persistent homotopy groups. As an application, we analyze the sublevelset persistent homotopy groups of the energy landscape of alkane molecules.

We explore emerging relationships between the Gromov-Hausdorff distance, Borsuk-Ulam theorems, and Vietoris-Rips simplicial complexes. The Gromov-Hausdorff distance between two metric spaces X and Y can be lower bounded by the distortion of (possibly discontinuous) functions between them. The more these functions must distort the metrics, the larger the Gromov-Hausdorff distance must be. Topology has few tools to obstruct the existence of discontinuous functions. However, an arbitrary function f: X → Y induces a continuous map between their Vietoris-Rips simplicial complexes, where the allowable choices of scale parameters depend on how much the function f distorts distances. We can then use equivariant topology to obstruct the existence of certain continuous maps between Vietoris-Rips complexes. With these ideas we bound how discontinuous an odd map between spheres S^k → Sⁿ with k>n must be, generalizing a result by Dubins and Schwarz (1981), which is the case k=n+1. As an application, we recover or improve upon all of the lower bounds from Lim, Mémoli, and Smith (2022) on the Gromov-Hausdorff distances between spheres of different dimensions. We also provide new upper bounds on the Gromov-Hausdorff distance between spheres of adjacent dimensions.

Suppose one wants to monitor a domain with sensors each sensing small ball-shaped regions, but the domain is hazardous enough that one cannot control the placement of the sensors. A prohibitively large number of randomly-placed sensors would be required to obtain static coverage. Instead, one can use fewer sensors by providing only mobile coverage, a generalization of the static setup wherein every possible intruder is detected by the moving sensors in a bounded amount of time. Here, we use topology in order to implement algorithms certifying mobile coverage that use only local data to solve the global problem. Our algorithms do not require knowledge of the sensors' locations. We experimentally study the statistics of mobile coverage in two dynamical scenarios. We allow the sensors to move independently (billiard dynamics and Brownian motion), or to locally coordinate their dynamics (collective animal motion models). Fewer sensors are required in the mobile setting. Our detailed simulations show, for example, that the expected time until mobile coverage is achieved increases more rapidly, as the sensing radius decreases, in the billiard motion model than in the D'Orsogna collective motion model.

Persistent homology has emerged as a novel tool for data analysis in the past two decades. However, there are still very few shapes or even manifolds whose persistent homology barcodes (say of the Vietoris-Rips complex) are fully known. Towards this direction, let P_n be the boundary of a regular polygon in the plane with n sides; we describe the homotopy types of Vietoris-Rips complexes of P_n. Indeed, when n=(2k+1)!! is an odd double factorial, we provide a complete characterization of the homotopy types and persistent homology of the Vietoris-Rips complexes of P_n up to a scale parameter r_n, where r_n approaches the diameter of P_n as n tends to infinity. Surprisingly, these homotopy types include spheres of all dimensions. Roughly speaking, the number of higher-dimensional spheres appearing is linked to the number of equilateral (but not necessarily equiangular) stars that can be inscribed into P_n. As our main tool we use the recently-developed theory of cyclic graphs and winding fractions. Furthermore, we show that the Vietoris-Rips complex of an arbitrarily dense subset of P_n need not be homotopy equivalent to the Vietoris-Rips complex of P_n itself, and indeed, these two complexes can have different homology groups in arbitrarily high dimensions. As an application of our results, we provide a lower bound on the Gromov-Hausdorff distance between P_n and the circle.

We introduce several geometric notions, including thick-thin decompositions and the width of a homology class, to the theory of persistent homology. These ideas provide geometric interpretations of persistence diagrams. Indeed, we give quantitative and geometric descriptions of the "size'' or "persistence'' of a homology class. As a case study, we analyze the power filtration on unweighted graphs, and provide explicit bounds for the life spans of homology classes in persistence diagrams in all dimensions.

We show that the size of codes in projective space controls structural results for zeros of odd maps from spheres to Euclidean space. In fact, this relation is given through the topology of the space of probability measures on the sphere whose supports have diameter bounded by some specific parameter. Our main result is a generalization of the Borsuk-Ulam theorem, and we derive four consequences of it: (i) We give a new proof of a result of Simonyi and Tardos on topological lower bounds for the circular chromatic number of a graph; (ii) we study generic embeddings of spheres into Euclidean space, and show that projective codes give quantitative bounds for a measure of genericity of sphere embeddings; and we prove generalizations of (iii) the Ham Sandwich theorem and (iv) the Lyusternik-Shnirel'man-Borsuk covering theorem for the case where the number of measures or sets in a covering, respectively, may exceed the ambient dimension.

A Čech complex of a finite simple graph G is a nerve complex of balls in the graph, with one ball centered at each vertex. More precisely, let the Čech complex N(G,r) be the nerve of all closed balls of radius r/2 centered at vertices of G, where these balls are drawn in the geometric realization of the graph G (equipped with the shortest path metric). The simplicial complex N(G,r) is equal to the graph G when r=1, and homotopy equivalent to the graph G when r is smaller than half the length of the shortest loop in G. For higher values of r, the topology of N(G,r) is not well-understood. We consider the n-dimensional hypercube graphs I_n with 2ⁿ vertices. Our main results are as follows. First, when r=2, we show that the Čech complex N(I_n,2) is homotopy equivalent to a wedge of 2-spheres for all n≥1, and we count the number of 2-spheres appearing in this wedge sum. Second, when r=3, we show that N(I_n,3) is homotopy equivalent to a simplicial complex of dimension at most 4, and that for n≥4 the reduced homology of N(I_n, 3) is nonzero in dimensions 3 and 4, and zero in all other dimensions. Finally, we show that for all n≥1 and r≥0, the inclusion N(I_n, r) → N(I_n, r+2) is null-homotopic, providing a bound on the length of bars in the persistent homology of Čech complexes of hypercube graphs.

A metric thickening of a given metric space X is any metric space admitting an isometric embedding of X. Thickenings have found use in applications of topology to data analysis, where one may approximate the shape of a dataset via the persistent homology of an increasing sequence of spaces. We introduce two new families of metric thickenings, the p-Vietoris-Rips and p-Čech metric thickenings for all 1≤ p≤ ∞, which include all measures on X whose p-diameter or p-radius is bounded from above, equipped with an optimal transport metric. The p-diameter (resp. p-radius) of a measure is a certain ℓ_p relaxation of the usual notion of diameter (resp. radius) of a subset of a metric space. These families recover the previously studied Vietoris-Rips and Čech metric thickenings when p=∞. As our main contribution, we prove a stability theorem for the persistent homology of p-Vietoris-Rips and p-Čech metric thickenings, which is novel even in the case p=∞. In the specific case p=2, we prove a Hausmann-type theorem for thickenings of manifolds, and we derive the complete list of homotopy types of the 2-Vietoris-Rips thickenings of the n-sphere as the scale increases.

We provide novel lower bounds on the Betti numbers of Vietoris-Rips complexes of hypercube graphs of all dimensions, and at all scales. In more detail, let Q_n be the vertex set of 2ⁿ vertices in the n-dimensional hypercube graph, equipped with the shortest path metric. Let VR(Q_n;r) be its Vietoris--Rips complex at scale parameter r ≥ 0, which has Q_n as its vertex set, and all subsets of diameter at most r as its simplices. For integers r ≤ r' the inclusion VR(Q_n;r) ↪ VR(Q_n;r') is nullhomotopic, meaning no persistent homology bars have length longer than one, and we therefore focus attention on the individual spaces VR(Q_n;r). We provide lower bounds on the ranks of homology groups of VR(Q_n;r). For example, using cross-polytopal generators, we prove that the rank of H_2^r-1(VR(Q_n;r)) is at least 2^n-(r+1)[n choose r+1]. We also prove a version of homology propagation: if q ≥ 1 and if p is the smallest integer for which rank H_q(VR(Q_p;r)) ≠ 0, then rank H_q(VR(Q_n;r)) ≥ ∑_i=pⁿ 2^i-p [i-1 choose p-1] · rank H_q(VR(Q_p;r)) for all n ≥ p. When r ≤ 3, this result and variants thereof provide tight lower bounds on the rank of H_q(VR(Q_n;r)) for all n, and for each r ≥ 4 we produce novel lower bounds on the ranks of homology groups. Furthermore, we show that for each r ≥ 2, the homology groups of VR(Q_n;r) for n ≥ 2r+1 contain propagated homology not induced by the initial cross-polytopal generators.

Recent work (J. Chem. Phys. 154, 114114) has demonstrated that sublevelset persistent homology provides a compact representation of the complex features of an energy landscape in 3N-dimensions. This includes information about all transition paths between local minima (connected by critical points of index ≥1), and allows for differentiation of energy landscapes that may appear similar when considering only the lowest energy pathways (as tracked by other representations like disconnectivity graphs using index 1 critical points). Using the additive nature of the conformational potential energy landscape of n-alkanes, it became apparent that some topological features --- such as the number of sublevelset persistence bars --- could be proven. This work expands the notion of predictable energy landscape topology to any additive intramolecular energy function, including the number of sublevelset persistent bars as well as the birth and death times of these topological features. This amounts to a rigorous methodology to predict the relative energies of all topological features of the conformational energy landscape in 3N dimensions (without the need for dimensionality reduction). This approach is demonstrated for branched alkanes of varying complexity and connectivity patterns. More generally, this result explains how the sublevelset persistent homology of an additive energy landscape can be computed from the individual terms comprising that landscape.

Topological data analysis (TDA) is a tool from data science and mathematics that is beginning to make waves in environmental science. In this work, we seek to provide an intuitive and understandable introduction to a tool from TDA that is particularly useful for the analysis of imagery, namely persistent homology. We briefly discuss the theoretical background but focus primarily on understanding the output of this tool and discussing what information it can glean. To this end, we frame our discussion around a guiding example of classifying satellite images from the Sugar, Fish, Flower, and Gravel Dataset produced for the study of mesocale organization of clouds by Rasp et. al. in 2020. We demonstrate how persistent homology and its vectorization, persistence landscapes, can be used in a workflow with a simple machine learning algorithm to obtain good results, and explore in detail how we can explain this behavior in terms of image-level features. One of the core strengths of persistent homology is how interpretable it can be, so throughout this paper we discuss not just the patterns we find, but why those results are to be expected given what we know about the theory of persistent homology. Our goal is that a reader of this paper will leave with a better understanding of TDA and persistent homology, be able to identify problems and datasets of their own for which persistent homology could be helpful, and gain an understanding of results they obtain from applying the included GitHub example code.

Let G be a group acting properly and by isometries on a metric space X; it follows that the quotient or orbit space X/G is also a metric space. We study the Vietoris-Rips and Čech complexes of X/G. Whereas (co)homology theories for metric spaces let the scale parameter of a Vietoris-Rips or Čech complex go to zero, and whereas geometric group theory requires the scale parameter to be sufficiently large, we instead consider intermediate scale parameters (neither tending to zero nor to infinity). As a particular case, we study the Vietoris-Rips and Čech thickenings of projective spaces at the first scale parameter where the homotopy type changes.

We study the relationship between metric thickenings and simplicial complexes associated to coverings of metric spaces. Let 𝒰 be a cover of a separable metric space X by open sets with a uniform diameter bound. The Vietoris complex contains all simplices with vertex set contained in some U ∈ 𝒰, and the Vietoris metric thickening is the space of probability measures with support in some U ∈ 𝒰, equipped with an optimal transport metric. We show that the Vietoris metric thickening and the Vietoris complex have isomorphic homotopy groups in all dimensions. In particular, by choosing the cover 𝒰 appropriately, we get isomorphisms between the homotopy groups of Vietoris-Rips metric thickenings and simplicial complexes, as well as between the homotopy groups of Čech metric thickenings and simplicial complexes.

We describe the homotopy types of Vietoris-Rips complexes of hypercube graphs at small scale parameters. In more detail, let Q_n be the vertex set of the hypercube graph with 2ⁿ vertices, equipped with the shortest path metric. Equivalently, Q_n is the set of all binary strings of length n, equipped with the Hamming distance. The Vietoris-Rips complex of Q_n at scale parameter zero is 2ⁿ points, and the Vietoris-Rips complex of Q_n at scale parameter one is the hypercube graph, which is homotopy equivalent to a wedge sum of circles. We show that the Vietoris-Rips complex of Q_n at scale parameter two is homotopy equivalent to a wedge sum of 3-spheres, and furthermore we provide a formula for the number of 3-spheres. Many questions about the Vietoris-Rips complexes of Q_n at larger scale parameters remain open.

A support vector machine (SVM) is an algorithm which finds a hyperplane that optimally separates labeled data points in Rⁿ into positive and negative classes. The data points on the margin of this separating hyperplane are called support vectors. We study the possible configurations of support vectors for points in general position. In particular, we connect the possible configurations to Radon's theorem, which provides guarantees for when a set of points can be divided into two classes (positive and negative) whose convex hulls intersect. If the positive and negative support vectors in a generic SVM configuration are projected to the separating hyperplane, then these projected points will form a Radon configuration. Further, with a particular type of general position, we show there are at most n+1 support vectors. This can be used to test the level of machine precision needed in a support vector machine implementation. We also show the projections of the convex hulls of the support vectors intersect in a single Radon point, and under a small enough perturbation, the points labeled as support vectors remain labeled as support vectors. We furthermore consider computations studying the expected number of support vectors for randomly generated data.

One approach to understanding complex data is to study its shape through the lens of algebraic topology. While the early development of topological data analysis focused primarily on static data, in recent years, theoretical and applied studies have turned to data that varies in time. A time-varying collection of metric spaces as formed, for example, by a moving school of fish or flock of birds, can contain a vast amount of information. There is often a need to simplify or summarize the dynamic behavior. We provide an introduction to topological summaries of time-varying metric spaces including vineyards, crocker plots, and multiparameter rank functions. We then introduce a new tool to summarize time-varying metric spaces: a crocker stack. Crocker stacks are convenient for visualization, amenable to machine learning, and satisfy a desirable stability property which we prove. We demonstrate the utility of crocker stacks for a parameter identification task involving an influential model of biological aggregations. Altogether, we aim to bring the broader applied mathematics community up-to-date on topological summaries of time-varying metric spaces.

A Vietoris-Rips complex is a way to thicken a (possibly discrete) metric space into a larger space containing more topological information. We prove that if C is a convex closed differentiable curve in the plane such that the convex hull of C contains the evolute of C, then the homotopy type of a Vietoris-Rips complex of a subset of n points from C can be computed in time O(n log n). Furthermore, we show how to compute the k-dimensional persistent homology of these n points in running time O(n²(k+log n)), which is nearly quadratic in the number of vertices n. This improves upon the traditional persistent homology algorithm, which is cubic in the number of simplices of dimension at most k+1, and hence of running time O(n^3(k+2)) in the number of vertices n. We ask if there are other geometric settings in which computing persistent homology is (say) quadratic or cubic in the number of vertices, instead of in the number of simplices.

The challenge of appropriately including many-body affects are well-known throughout the electronic structure and condensed matter scientific communities. Describing the interactions amongst particles (be they electrons, molecules, colloids...) beyond simple pairwise correlations underpins the most pressing theoretical and modeling tasks of our generation. Accurate many-body theories are required to predict and understand phenomena that traverse length and timescales - from the behavior of quantum materials to photosynthesis. This Outlook provides a fresh perspective on the development of new theories that leverage the most recent advances to data science - a roadmap of how graph theory, computational topology, machine learning, and other methods are dramatically accelerating scientific innovation. Historical emphasis has been placed upon many-body methods at the smallest scale of electrons (partially inspired by Feynman's famous lecture of 1959 entitled "There's Plenty of Room at the Bottom: An Invitation to Enter a New Field of Physics''). However advanced modeling and simulation capabilities, alongside mathematical methods that identify complex multidimensional correlations, create a framework for expanding our consideration of many-body affects to systems that approach realistic complexity and size and evolve across timescales of many orders of magnitude - a "Middle Science''.

Suppose each vertex of a graph is originally occupied by contamination, except for those vertices occupied by lions. As the lions wander on the graph, they clear the contamination from each vertex they visit. However, the contamination simultaneously spreads to any adjacent vertex not occupied by a lion. How many lions are required in order to clear the graph of contamination? We give a lower bound on the number of lions needed in terms of the Cheeger constant of the graph. Furthermore, the lion and contamination problem has been studied in detail on square grid graphs by Brass et al. and Berger et al., and we extend this analysis to the setting of triangular grid graphs.

Through the use of examples, we explain one way in which applied topology has evolved since the birth of persistent homology in the early 2000s. The first applications of topology to data emphasized the global shape of a dataset, such as the three-circle model for 3x3 pixel patches from natural images, or the configuration space of the cyclo-octane molecule, which is a sphere with a Klein bottle attached via two circles of singularity. In these studies of global shape, short persistent homology bars are disregarded as sampling noise. More recently, however, persistent homology has been used to address questions about the local geometry of data. For instance, how can local geometry be vectorized for use in machine learning problems? Persistent homology and its vectorization methods, including persistence landscapes and persistence images, provide popular techniques for incorporating both local geometry and global topology into machine learning. Our meta-hypothesis is that the short bars are as important as the long bars for many machine learning tasks. In defense of this claim, we survey applications of persistent homology to shape recognition, agent-based modeling, materials science, archaeology, and biology. Additionally, we survey work connecting persistent homology to geometric features of spaces, including curvature and fractal dimension, and various methods that have been used to incorporate persistent homology into machine learning.

Encoding the complex features of an energy landscape is a challenging task, and often chemists pursue the most salient features (minima and barriers) along a highly reduced space, i.e. 2- or 3-dimensions. Even though disconnectivity graphs or merge trees summarize the connectivity of the local minima of an energy landscape via the lowest-barrier pathways, there is more information to be gained by also considering the topology of each connected component at different energy thresholds (or sublevelsets). We propose sublevelset persistent homology as an appropriate tool for this purpose. Our computations on the configuration phase space of n-alkanes from butane to octane allow us to conjecture, and then prove, a complete characterization of the sublevelset persistent homology of the alkane C_m H_2m+2 potential energy landscapes, for all m, and in all homological dimensions. We further compare both the analytical configurational potential energy landscapes and sampled data from molecular dynamics simulation, using the united and all-atom descriptions of the intramolecular interactions. In turn, this supports the application of distance metrics to quantify sampling fidelity and lays the foundation for future work regarding new metrics that quantify differences between the topological features of high-dimensional energy landscapes.

In today's data-driven world, data completion is essential whether it is the main goal or a pre-processing step. Structured matrix completion includes any setting in which data is not missing uniformly at random. In recent work, a modification to the standard nuclear norm minimization (NNM) for matrix completion has been developed to take into account sparsity-based structure in the missing entries. This notion of structure is motivated in many settings including recommender systems, where the probability that an entry is observed or not depends on the value of the entry. We propose adjusting an Iteratively Reweighted Least Squares (IRLS) algorithm for low-rank matrix completion to take into account sparsity-based structure in the missing entries. We also present an iterative gradient-projection-based implementation of the algorithm that can handle large-scale matrices. Finally, we present a robust array of numerical experiments on matrices of varying sizes, ranks, and level of structure. We show that our proposed method is comparable with the adjusted NNM on small structured matrices. Further, we show that our proposed method often outperforms the IRLS algorithm in structured settings on matrices up to size 1000×1000.

Many simplicial complexes arising in practice have an associated metric space structure on the vertex set but not on the complex, e.g. the Vietoris-Rips complex in applied topology. We formalize a remedy by introducing a category of simplicial metric thickenings whose objects have a natural realization as metric spaces. The properties of this category allow us to prove that, for a large class of thickenings including Vietoris-Rips and Čech thickenings, the product of metric thickenings is homotopy equivalent to the metric thickenings of product spaces, and similarly for wedge sums.

Thickenings of a metric space capture local geometric properties of the space. Here we exhibit applications of lower bounding the topology of thickenings of the circle and more generally the sphere. We explain interconnections with the geometry of circle actions on Euclidean space, the structure of zeros of trigonometric polynomials, and theorems of Borsuk-Ulam type. We use the combinatorial and geometric structure of the convex hull of orbits of circle actions on Euclidean space to give geometric proofs of the homotopy type of metric thickenings of the circle. Homotopical connectivity bounds of thickenings of the sphere allow us to prove that a weighted average of function values of odd maps Sⁿ → Rⁿ⁺² on a small diameter set is zero. We prove an additional generalization of the Borsuk-Ulam theorem for odd maps S^2n-1 → R^2kn+2n-1. We prove such results for odd maps from the circle to any Euclidean space with optimal quantitative bounds. This in turn implies that any raked homogeneous trigonometric polynomial has a zero on a subset of the circle of a specific diameter; these results are optimal.

We use persistent homology in order to define a family of fractal dimensions, denoted dim_PHⁱ(μ) for each homological dimension i ≥ 0, assigned to a probability measure μ on a metric space. The case of 0-dimensional homology (i=0) relates to work by Michael J Steele (1988) studying the total length of a minimal spanning tree on a random sampling of points. Indeed, if μ is supported on a compact subset of Euclidean space R^m for m ≥ 2, then Steele's work implies that dim_PH⁰(μ)=m if the absolutely continuous part of μ has positive mass, and otherwise dim_PHPH⁰(μ)<m. Experiments suggest that similar results may be true for higher-dimensional homology 0<i<m, though this is an open question. Our fractal dimension is defined by considering a limit, as the number of points n goes to infinity, of the total sum of the i-dimensional persistent homology interval lengths for n random points selected from μ in an i.i.d. fashion. To some measures μ, we are able to assign a finer invariant, a curve measuring the limiting distribution of persistent homology interval lengths as the number of points goes to infinity. We prove this limiting curve exists in the case of 0-dimensional homology when n is the uniform distribution over the unit interval, and conjecture that it exists when n is the rescaled probability measure for a compact set in Euclidean space with positive Lebesgue measure.

We study Vietoris-Rips and Čech complexes of metric wedge sums and metric gluings. We show that the Vietoris-Rips (resp. Čech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the Vietoris-Rips (resp. Čech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the Vietoris-Rips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the Vietoris-Rips complexes of a wide class of metric graphs.

Multidimensional scaling (MDS) is a popular technique for mapping a finite metric space into a low-dimensional Euclidean space in a way that best preserves pairwise distances. We overview the theory of classical MDS, along with its optimality properties and goodness of fit. Further, we present a notion of MDS on infinite metric measure spaces that generalizes these optimality properties. As a consequence we can study the MDS embeddings of the geodesic circle S¹ into R^m for all m, and ask questions about the MDS embeddings of the geodesic n-spheres Sⁿ into R^m. Furthermore, we address questions on convergence of MDS. For instance, if a sequence of metric measure spaces converges to a fixed metric measure space X, then in what sense do the MDS embeddings of these spaces converge to the MDS embedding of X?

We propose a torus model for high-contrast patches of optical flow. Our model is derived from a database of ground-truth optical flow from the computer-generated video Sintel, collected by Butler et al. in A naturalistic open source movie for optical flow evaluation. Using persistent homology and zigzag persistence, popular tools from the field of computational topology, we show that the high-contrast 3×3 patches from this video are well-modeled by a torus, a nonlinear 2-dimensional manifold. Furthermore, we show that the optical flow torus model is naturally equipped with the structure of a fiber bundle, related to the statistics of range image patches.

Given a sample X from an unknown manifold M embedded in Euclidean space, it is possible to recover the homology groups of M by building a Vietoris-Rips or Čech simplicial complex on top of the vertex set X. However, these simplicial complexes need not inherit the metric structure of the manifold, in particular when X is infinite. Indeed, a simplicial complex is not even metrizable if it is not locally finite. We instead consider metric thickenings of X, called the Vietoris-Rips and Čech thickenings, which are equipped with the 1-Wasserstein metric in place of the simplicial complex topology. We show that for Euclidean subsets M with positive reach, the thickenings satisfy metric analogues of Hausmann's theorem and the nerve lemma (the metric Vietoris-Rips and Čech thickenings of M are homotopy equivalent to M for scale parameters less than the reach). In contrast to Hausmann's original result, our homotopy equivalence is a deformation retraction, is realized by canonical maps in both directions, and furthermore can be proven to be a homotopy equivalence via simple linear homotopies from the map compositions to the corresponding identity maps.

For X a metric space and r > 0 a scale parameter, the Vietoris-Rips complex VR_<(X;r) (resp. VR_≤(X;r)) has X as its vertex set, and a finite subset σ of X as a simplex whenever the diameter of σ is less than r (resp. at most r). Though Vietoris-Rips complexes have been studied at small choices of scale by Hausmann and Latschev, they are not well-understood at larger scale parameters. In this paper we investigate the homotopy types of Vietoris-Rips complexes of ellipses Y={(x,y) ∈ R² | (x/a)²+y²=1} of small eccentricity, meaning 1 < a ≤ √2. Indeed, we show there are constants r₁ < r₂ such that for all r₁ < r < r₂, we have VR_<(Y;r) ≃ S² and VR_≤(X;r) ≃ ∨⁵ S², though only one of the two-spheres in VR_≤(X;r) is persistent. Furthermore, we show that for any scale parameter r₁ < r < r₂, there are arbitrarily dense subsets of the ellipse such that the Vietoris-Rips complex of the subset is not homotopy equivalent to the Vietoris-Rips complex of the entire ellipse. As our main tool we link these homotopy types to the structure of infinite cyclic graphs.

Given a sample of points X in a metric space M and a scale r > 0, the Vietoris-Rips simplicial complex VR(X;r) is a standard construction to attempt to recover M from X up to homotopy type. A deficiency of this approach is that VR(X;r) is not metrizable if it is not locally finite, and thus does not recover metric information about M. We attempt to remedy this shortcoming by defining a metric space thickening of X, which we call the Vietoris-Rips thickening VR^m(X;r), via the theory of optimal transport. When M is a complete Riemannian manifold, or alternatively a compact Hadamard space, we show that the Vietoris-Rips thickening satisfies Hausmann's theorem (VR^m(M;r) ≃ M for r sufficiently small) with a simpler proof than Hausmann's original result: homotopy equivalence VR^m(M;r) → M is canonically defined as a center of mass map, and its homotopy inverse is the (now continuous) inclusion map M ↪ VR^m(M;r). Furthermore, we describe the homotopy type of the Vietoris-Rips thickening of the n-sphere at the first positive scale parameter r where the homotopy type changes.

Let D be a Jordan domain in the plane. We consider a pursuit-evasion, contamination clearing, or sensor sweep problem in which the pursuer at each point in time is modeled by a continuous curve, called the sensor curve. Both time and space are continuous, and the intruders are invisible to the pursuer. Given D, what is the shortest length of a sensor curve necessary to provide a sweep of domain D, so that no continuously-moving intruder in D can avoid being hit by the curve? We define this length to be the sweeping cost of D. We provide an analytic formula for the sweeping cost of any Jordan domain in terms of the geodesic Fréchet distance between two curves on the boundary of D with non-equal winding numbers. As a consequence, we show that the sweeping cost of any convex domain is equal to its width, and that a convex domain of unit area with maximal sweeping cost is the equilateral triangle.

Many datasets can be viewed as a noisy sampling of an underlying space, and tools from topological data analysis can characterize this structure for the purpose of knowledge discovery. One such tool is persistent homology, which provides a multiscale description of the homological features within a dataset. A useful representation of this homological information is a persistence diagram (PD). Efforts have been made to map PDs into spaces with additional structure valuable to machine learning tasks. We convert a PD to a finite-dimensional vector representation which we call a persistence image (PI), and prove the stability of this transformation with respect to small perturbations in the inputs. The discriminatory power of PIs is compared against existing methods, showing significant performance gains. We explore the use of PIs with vector-based machine learning tools, such as linear sparse support vector machines, which identify features containing discriminating topological information. Finally, high accuracy inference of parameter values from the dynamic output of a discrete dynamical system (the linked twist map) and a partial differential equation (the anisotropic Kuramoto-Sivashinsky equation) provide a novel application of the discriminatory power of PIs.

Given a metric space X and a distance threshold r > 0, the Vietoris-Rips simplicial complex has as its simplices the finite subsets of X of diameter less than r. A theorem of Jean-Claude Hausmann states that if X is a Riemannian manifold and r is sufficiently small, then the Vietoris-Rips complex is homotopy equivalent to the original manifold. Little is known about the behavior of Vietoris-Rips complexes for larger values of r, even though these complexes arise naturally in applications using persistent homology. We show that as r increases, the Vietoris-Rips complex of the circle obtains the homotopy types of the circle, the 3-sphere, the 5-sphere, the 7-sphere, ..., until finally it is contractible. As our main tool we introduce a directed graph invariant, the winding fraction, which in some sense is dual to the circular chromatic number. Using the winding fraction we classify the homotopy types of the Vietoris-Rips complex of an arbitrary (possibly infinite) subset of the circle, and we study the expected homotopy type of the Vietoris-Rips complex of a uniformly random sample from the circle. Moreover, we show that as the distance parameter increases, the ambient Čech complex of the circle also obtains the homotopy types of the circle, the 3-sphere, the 5-sphere, the 7-sphere, ..., until finally it is contractible.

For X a finite subset of the circle and for 0 < r ≤ 1 fixed, consider the function f_r : X → X which maps each point to the clockwise furthest element of X within angular distance less than 2πr. We study the discrete dynamical system on X generated by f_r , and especially its expected behavior when X is a large random set. We show that, as |X| → ∞, the expected fraction of periodic points of f_r tends to 0 if r is irrational and to 1/q if r = p/q is rational with p and q coprime. These results are obtained via more refined statistics of f_r which we compute explicitly in terms of (generalized) Catalan numbers. The motivation for studying f_r comes from Vietoris-Rips complexes, a geometric construction used in computational topology. Our results determine how much one can expect to simplify the Vietoris-Rips complex of a random sample of the circle by removing dominated vertices.

We show that the nerve complex of n arcs in the circle is homotopy equivalent to either a point, an odd-dimensional sphere, or a wedge sum of spheres of the same even dimension. Moreover this homotopy type can be computed in time O(n log n). For the particular case of the nerve complex of evenly-spaced arcs of the same length, we determine the dihedral group action on homology, and we relate the complex to a cyclic polytope with n vertices. We give three applications of our knowledge of the homotopy types of nerve complexes of circular arcs. First, we use the connection to cyclic polytopes to give a novel topological proof of a known upper bound on the distance between successive roots of a homogeneous trigonometric polynomial. Second, we show that the Lovász bound on the chromatic number of a circular complete graph is either sharp or off by one. Third, we show that the Vietoris-Rips simplicial complex of n points in the circle is homotopy equivalent to either a point, an odd-dimensional sphere, or a wedge sum of spheres of the same even dimension, and furthermore this homotopy type can be computed in time O(n log n).

Suppose that ball-shaped sensors wander in a bounded domain. A sensor doesn't know its location but does know when it overlaps a nearby sensor. We say that an evasion path exists in this sensor network if a moving intruder can avoid detection. In "Coordinate-free coverage in sensor networks with controlled boundaries via homology", Vin de Silva and Robert Ghrist give a necessary condition, depending only on the time-varying connectivity data of the sensors, for an evasion path to exist. Using zigzag persistent homology, we provide an equivalent condition that moreover can be computed in a streaming fashion. However, no method with time-varying connectivity data as input can give necessary and sufficient conditions for the existence of an evasion path. Indeed, we show that the existence of an evasion path depends not only on the fibrewise homotopy type of the region covered by sensors but also on its embedding in spacetime. For planar sensors that also measure weak rotation and distance information, we provide necessary and sufficient conditions for the existence of an evasion path.

We use the nudged elastic band method from computational chemistry to analyze high-dimensional data. Our approach is inspired by Morse theory, and as output we produce an increasing sequence of small cell complexes modeling the dense regions of the data. We test the method on data sets arising in social networks and in image processing. Furthermore, we apply the method to identify new topological structure in a data set of optical flow patches.

The computation of persistent homology has proven a fundamental component of the nascent field of topological data analysis and computational topology. We describe a new software package for topological computation, with design focus on needs of the research community. This tool, replacing previous jPlex and Plex, enables researchers to access state of the art algorithms for persistent homology, cohomology, hom complexes, filtered simplicial complexes, filtered cell complexes, witness complex constructions, and many more essential components of computational topology. We describe the design goals we have chosen, the resulting software package, and some of its more novel capabilities.

Carlsson, Ishkanov, de Silva, and Zomorodian apply computational topological tools to the data set of 3 × 3 patches from optical images studied by Lee, Pedersen, and Mumford and find geometric structures for high density subsets. One high density subset is called the primary circle and essentially consists of patches with a line separating a light and a dark region. In this paper, we apply the techniques of Carlsson et al. to range patches. By enlarging to 5 × 5 and 7 × 7 patches, we find core subsets that have the topology of the primary circle, suggesting a stronger connection between optical patches and range patches than was found by Lee, Pedersen, and Mumford.