@inproceedings{17146, abstract = {The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions, which prove that this upper bound is asymptotically tight. For example, we describe a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of the Čech complex at the other radius is n². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry.}, author = {Edelsbrunner, Herbert and Pach, János}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Maximum Betti numbers of Čech complexes}}, doi = {10.4230/LIPIcs.SoCG.2024.53}, volume = {293}, year = {2024}, } @inproceedings{17145, abstract = {Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.}, author = {Rote, Günter and Rüber, Moritz and Saghafian, Morteza}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Grid peeling of parabolas}}, doi = {10.4230/LIPIcs.SoCG.2024.76}, volume = {293}, year = {2024}, } @article{17891, abstract = {Abstract Methods used in topological data analysis naturally capture higher-order interactions in point cloud data embedded in a metric space. This methodology was recently extended to data living in an information space, by which we mean a space measured with an information theoretical distance. One such setting is a finite collection of discrete probability distributions embedded in the probability simplex measured with the relative entropy (Kullback–Leibler divergence). More generally, one can work with a Bregman divergence parameterized by a different notion of entropy. While theoretical algorithms exist for this setup, there is a paucity of implementations for exploring and comparing geometric-topological properties of various information spaces. The interest of this work is therefore twofold. First, we propose the first robust algorithms and software for geometric and topological data analysis in information space. Perhaps surprisingly, despite working with Bregman divergences, our design reuses robust libraries for the Euclidean case. Second, using the new software, we take the first steps towards understanding the geometric-topological structure of these spaces. In particular, we compare them with the more familiar spaces equipped with the Euclidean and Fisher metrics.}, author = {Edelsbrunner, Herbert and Ölsböck, Katharina and Wagner, Hubert}, issn = {1099-4300}, journal = {Entropy}, number = {8}, publisher = {MDPI}, title = {{Understanding higher-order interactions in information space}}, doi = {10.3390/e26080637}, volume = {26}, year = {2024}, } @inproceedings{15012, abstract = {We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n-1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs.}, author = {Pach, János and Saghafian, Morteza and Schnider, Patrick}, booktitle = {31st International Symposium on Graph Drawing and Network Visualization}, isbn = {9783031492716}, issn = {1611-3349}, location = {Isola delle Femmine, Palermo, Italy}, pages = {339--346}, publisher = {Springer Nature}, title = {{Decomposition of geometric graphs into star-forests}}, doi = {10.1007/978-3-031-49272-3_23}, volume = {14465}, year = {2024}, } @article{17190, abstract = {For a locally finite set, 𝐴⊆ℝ𝑑 , the 𝑘 th Brillouin zone of 𝑎∈𝐴 is the region of points 𝑥∈ℝ𝑑 for which ‖𝑥−𝑎‖ is the 𝑘 th smallest among the Euclidean distances between 𝑥 and the points in 𝐴 . If 𝐴 is a lattice, the 𝑘 th Brillouin zones of the points in 𝐴 are translates of each other, and together they tile space. Depending on the value of 𝑘 , they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in ℝ2 , and the convergence of the maximum volume of a chamber to zero for the integer lattice.}, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafaris, Mohadese and Heiss, Teresa and Saghafiant, Morteza and Wintraecken, Mathijs}, issn = {0895-4801}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, pages = {1784--1807}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Brillouin zones of integer lattices and their perturbations}}, doi = {10.1137/22M1489071}, volume = {38}, year = {2024}, } @inproceedings{18556, abstract = {Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, booktitle = {32nd International Symposium on Graph Drawing and Network Visualization}, isbn = {9783959773430}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The Euclidean MST-ratio for bi-colored lattices}}, doi = {10.4230/LIPIcs.GD.2024.3}, volume = {320}, year = {2024}, } @inproceedings{18097, abstract = {In our companion paper "Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.}, author = {Attali, Dominique and Kourimska, Hana and Fillmore, Christopher D and Ghosh, Ishika and Lieutier, Andre and Stephenson, Elizabeth R and Wintraecken, Mathijs}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The ultimate frontier: An optimality construction for homotopy inference (media exposition)}}, doi = {10.4230/LIPIcs.SoCG.2024.87}, volume = {293}, year = {2024}, } @article{13182, abstract = {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.}, author = {Biswas, Ranita and Cultrera Di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {2367-1734}, journal = {Journal of Applied and Computational Topology}, pages = {1101--1119}, publisher = {Springer Nature}, title = {{Geometric characterization of the persistence of 1D maps}}, doi = {10.1007/s41468-023-00126-9}, volume = {8}, year = {2024}, } @article{15380, abstract = {The depth of a cell in an arrangement of n (non-vertical) great-spheres in Sd is the number of great-spheres that pass above the cell. We prove Euler-type relations, which imply extensions of the classic Dehn–Sommerville relations for convex polytopes to sublevel sets of the depth function, and we use the relations to extend the expressions for the number of faces of neighborly polytopes to the number of cells of levels in neighborly arrangements.}, author = {Biswas, Ranita and Cultrera Di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {2367-1734}, journal = {Journal of Applied and Computational Topology}, pages = {557--578}, publisher = {Springer Nature}, title = {{Depth in arrangements: Dehn–Sommerville–Euler relations with applications}}, doi = {10.1007/s41468-024-00173-w}, volume = {8}, year = {2024}, } @article{15247, abstract = {Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erdős–Szemerédi conjecture, recently proved by Naslund and Sawin, that there is a constant <2 such that every family of subsets of an n-element set that contains no odd-sunflower consists of at most n sets. We construct such families of size at least 1.5021n. We also characterize minimal odd-sunflowers of triples.}, author = {Frankl, Peter and Pach, János and Pálvölgyi, Dömötör}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory, Series A}, number = {8}, publisher = {Elsevier}, title = {{Odd-sunflowers}}, doi = {10.1016/j.jcta.2024.105889}, volume = {206}, year = {2024}, } @phdthesis{18667, abstract = {Many chemical and physical properties of materials are determined by the material’s shape, for example the size of its pores and the width of its tunnels. This makes materials science a prime application area for geometrical and topological methods. Nevertheless many methods in topological data analysis have not been satisfyingly extended to the needs of materials science. This thesis provides new methods and new mathematical theorems targeted at those specific needs by answering four different research questions. While the motivation for each of the research questions arises from materials science, the methods are versatile and can be applied in different areas as well. The first research question is concerned with image data, for example a three-dimensional computed tomography (CT) scan of a material, like sand or stone. There are two commonly used topologies for digital images and depending on the application either of them might be required. However, software for computing the topological data analysis method persistence homology, usually supports only one of the two topologies. We answer the question how to compute persistent homology of an image with respect to one of the two topologies using software that is intended for the other topology. The second research question is concerned with image data as well, and asks how much of the topological information of an image is lost when the resolution is coarsened. As computer tomography scanners are more expensive the higher the resolution, it is an important question in materials science to know which resolution is enough to get satisfying persistent homology. We give theoretical bounds on the information loss based on different geometrical properties of the object to be scanned. In addition, we conduct experiments on sand and stone CT image data. The third research question is motivated by comparing crystalline materials efficiently. As the atoms within a crystal repeat periodically, crystalline materials are either modeled by unmanageable infinite periodic point sets, or by one of their fundamental domains, which is unstable under perturbation. Therefore a fingerprint of crystalline materials is needed, with appropriate properties such that comparing the crystals can be eased by comparing the fingerprints instead. We define the density fingerprint and prove the necessary properties. The fourth research question is motivated by studying the hole-structure or connectedness, i.e. persistent homology or merge trees, of crystalline materials. A common way to deal with periodicity is to take a fundamental domain and identify opposite boundaries to form a torus. However, computing persistent homology or merge trees on that torus loses some of the information materials scientists are interested in and is additionally not stable under certain noise. We therefore decorate the merge tree stemming from the torus with additional information describing the density and growth rate of the periodic copies of a component within a growing spherical window. We prove all desired properties, like stability and efficient computability.}, author = {Heiss, Teresa}, isbn = {978-3-99078-052-7}, issn = {2663-337X}, keywords = {persistent homology, topological data analysis, periodic, crystalline materials, images, fingerprint}, pages = {111}, publisher = {Institute of Science and Technology Austria}, title = {{New methods for applying topological data analysis to materials science}}, doi = {10.15479/at:ista:18667}, year = {2024}, } @phdthesis{15094, abstract = {Point sets, geometric networks, and arrangements of hyperplanes are fundamental objects in discrete geometry that have captivated mathematicians for centuries, if not millennia. This thesis seeks to cast new light on these structures by illustrating specific instances where a topological perspective, specifically through discrete Morse theory and persistent homology, provides valuable insights. At first glance, the topology of these geometric objects might seem uneventful: point sets essentially lack of topology, arrangements of hyperplanes are a decomposition of Rd, which is a contractible space, and the topology of a network primarily involves the enumeration of connected components and cycles within the network. However, beneath this apparent simplicity, there lies an array of intriguing structures, a small subset of which will be uncovered in this thesis. Focused on three case studies, each addressing one of the mentioned objects, this work will showcase connections that intertwine topology with diverse fields such as combinatorial geometry, algorithms and data structures, and emerging applications like spatial biology. }, author = {Cultrera di Montesano, Sebastiano}, issn = {2663-337X}, pages = {108}, publisher = {Institute of Science and Technology Austria}, title = {{Persistence and Morse theory for discrete geometric structures}}, doi = {10.15479/at:ista:15094}, year = {2024}, } @inproceedings{15093, abstract = {We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right.}, author = {Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Henzinger, Monika H and Ost, Lara}, booktitle = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, editor = {Woodruff, David P.}, location = {Alexandria, VA, USA}, pages = {243 -- 295}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Dynamically maintaining the persistent homology of time series}}, doi = {10.1137/1.9781611977912.11}, year = {2024}, } @unpublished{18981, abstract = {We establish several results combining discrete Morse theory and microlocal sheaf theory in the setting of finite posets and simplicial complexes. Our primary tool is a computationally tractable description of the bounded derived category of sheaves on a poset with the Alexandrov topology. We prove that each bounded complex of sheaves on a finite poset admits a unique (up to isomorphism of complexes) minimal injective resolution, and we provide algorithms for computing minimal injective resolution of an injective complex, as well as several useful functors between derived categories of sheaves. For the constant sheaf on a simplicial complex, we give asymptotically tight bounds on the complexity of computing the minimal injective resolution using those algorithms. Our main result is a novel definition of the discrete microsupport of a bounded complex of sheaves on a finite poset. We detail several foundational properties of the discrete microsupport, as well as a microlocal generalization of the discrete homological Morse theorem and Morse inequalities.}, author = {Brown, Adam and Draganov, Ondrej}, booktitle = {arXiv}, title = {{Discrete microlocal Morse theory}}, doi = {10.48550/arXiv.2209.14993}, year = {2024}, } @unpublished{18673, abstract = {Motivated by applications to crystalline materials, we generalize the merge tree and the related barcode of a filtered complex to the periodic setting in Euclidean space. They are invariant under isometries, changing bases, and indeed changing lattices. In addition, we prove stability under perturbations and provide an algorithm that under mild geometric conditions typically satisfied by crystalline materials takes O((n+m)logn) time, in which n and m are the numbers of vertices and edges in the quotient complex, respectively. }, author = {Edelsbrunner, Herbert and Heiss, Teresa}, booktitle = {arXiv}, title = {{Merge trees of periodic filtrations}}, doi = {10.48550/arXiv.2408.16575}, year = {2024}, } @unpublished{15091, abstract = {Motivated by applications in the medical sciences, we study finite chromatic sets in Euclidean space from a topological perspective. Based on the persistent homology for images, kernels and cokernels, we design provably stable homological quantifiers that describe the geometric micro- and macro-structure of how the color classes mingle. These can be efficiently computed using chromatic variants of Delaunay and alpha complexes, and code that does these computations is provided.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, booktitle = {arXiv}, title = {{Chromatic alpha complexes}}, doi = {10.48550/arXiv.2212.03128}, year = {2024}, } @article{18564, abstract = {The recently discovered Pa 30 nebula, the putative type Iax supernova remnant associated with the historical supernova of 1181 AD, shows puzzling characteristics that make it unique among known supernova remnants. In particular, Pa 30 exhibits a complex morphology, with a unique radial and filamentary structure, and it hosts a hot stellar remnant at its center, which displays oxygen-dominated, ultrafast winds. Because of the surviving stellar remnant and the lack of hydrogen and helium in its filaments, it has been suggested that Pa 30 is the product of a failed thermonuclear explosion in a near- or super-Chandrasekhar white dwarf, which created a subluminous transient, a rare subtype of the Ia class of supernovae called type Iax. We present here a detailed study of the 3D structure and velocities of a full radial section of the remnant. The Integral Field Unit observations, obtained with the new red channel of the Keck Cosmic Web Imager spectrograph, reveal that the ejecta are consistent with being ballistic, with velocities close to the free-expansion velocity. Additionally, we detect a large cavity inside the supernova remnant and a sharp inner edge to the filamentary structure, which coincides with the outer edge of a bright ring detected in infrared images. Finally, we detect a strong asymmetry in the amount of ejecta along the line of sight, which might hint at an asymmetric explosion. Our analysis provides strong confirmation that the explosion originated from SN 1181.}, author = {Cunningham, Tim and Caiazzo, Ilaria and Prusinski, Nikolaus Z. and Fuller, James and Raymond, John C. and Kulkarni, S. R. and Neill, James D. and Duffell, Paul and Martin, Chris and Toloza, Odette and Charbonneau, David and Kenyon, Scott J. and Lin, Zeren and Matuszewski, Mateusz and McGurk, Rosalie and Polin, Abigail and Yao, Philippe Z.}, issn = {2041-8213}, journal = {The Astrophysical Journal Letters}, number = {1}, publisher = {IOP Publishing}, title = {{Expansion properties of the young supernova type Iax remnant Pa 30 revealed}}, doi = {10.3847/2041-8213/ad713b}, volume = {975}, year = {2024}, } @article{18709, abstract = {We measure the mass distribution of main-sequence (MS) companions to hot subdwarf B stars (sdBs) in post-common envelope binaries (PCEBs). We carried out a spectroscopic survey of 14 eclipsing systems ("HW Vir binaries") with orbital periods of 3.8 < Porb < 12 hr, resulting in a well-understood selection function and a near-complete sample of HW Vir binaries with G < 16. We constrain companion masses from the radial velocity curves of the sdB stars. The companion mass distribution peaks at MMS ≈ 0.15 M⊙ and drops off at MMS > 0.2 M⊙, with only two systems hosting companions above the fully convective limit. There is no correlation between Porb and MMS within the sample. A similar drop-off in the companion mass distribution of white dwarf (WD) + MS PCEBs has been attributed to disrupted magnetic braking (MB) below the fully convective limit. We compare the sdB companion mass distribution to predictions of binary evolution simulations with a range of MB laws. Because sdBs have short lifetimes compared to WDs, explaining the lack of higher-mass MS companions to sdBs with disrupted MB requires MB to be boosted by a factor of 20–100 relative to MB laws inferred from the rotation evolution of single stars. We speculate that such boosting may be a result of irradiation-driven enhancement of the MS stars' winds. An alternative possibility is that common envelope evolution favors low-mass companions in short-period orbits, but the existence of massive WD companions to sdBs with similar periods disfavors this scenario.}, author = {Blomberg, Lisa and El-Badry, Kareem and Breivik, Katelyn and Caiazzo, Ilaria and Nagarajan, Pranav and Rodriguez, Antonio and Van Roestel, Jan and Vanderbosch, Zachary P. and Yamaguchi, Natsuko}, issn = {0004-6280}, journal = {Publications of the Astronomical Society of the Pacific}, number = {12}, publisher = {IOP Publishing}, title = {{The companion mass distribution of post common envelope hot subdwarf binaries: Evidence for boosted and disrupted magnetic braking?}}, doi = {10.1088/1538-3873/ad94a2}, volume = {136}, year = {2024}, } @article{15372, abstract = {CRISPR-Cas9 is a powerful tool for genome editing, but the strict requirement for an NGG protospacer-adjacent motif (PAM) sequence immediately next to the DNA target limits the number of editable genes. Recently developed Cas9 variants have been engineered with relaxed PAM requirements, including SpG-Cas9 (SpG) and the nearly PAM-less SpRY-Cas9 (SpRY). However, the molecular mechanisms of how SpRY recognizes all potential PAM sequences remains unclear. Here, we combine structural and biochemical approaches to determine how SpRY interrogates DNA and recognizes target sites. Divergent PAM sequences can be accommodated through conformational flexibility within the PAM-interacting region, which facilitates tight binding to off-target DNA sequences. Nuclease activation occurs ~1000-fold slower than for Streptococcus pyogenes Cas9, enabling us to directly visualize multiple on-pathway intermediate states. Experiments with SpG position it as an intermediate enzyme between Cas9 and SpRY. Our findings shed light on the molecular mechanisms of PAMless genome editing.}, author = {Hibshman, Grace N. and Bravo, Jack Peter Kelly and Hooper, Matthew M. and Dangerfield, Tyler L. and Zhang, Hongshan and Finkelstein, Ilya J. and Johnson, Kenneth A. and Taylor, David W.}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Unraveling the mechanisms of PAMless DNA interrogation by SpRY-Cas9}}, doi = {10.1038/s41467-024-47830-3}, volume = {15}, year = {2024}, } @article{17442, abstract = {Although eukaryotic Argonautes have a pivotal role in post-transcriptional gene regulation through nucleic acid cleavage, some short prokaryotic Argonaute variants (pAgos) rely on auxiliary nuclease factors for efficient foreign DNA degradation1. Here we reveal the activation pathway of the DNA defence module DdmDE system, which rapidly eliminates small, multicopy plasmids from the Vibrio cholerae seventh pandemic strain (7PET)2. Through a combination of cryo-electron microscopy, biochemistry and in vivo plasmid clearance assays, we demonstrate that DdmE is a catalytically inactive, DNA-guided, DNA-targeting pAgo with a distinctive insertion domain. We observe that the helicase-nuclease DdmD transitions from an autoinhibited, dimeric complex to a monomeric state upon loading of single-stranded DNA targets. Furthermore, the complete structure of the DdmDE–guide–target handover complex provides a comprehensive view into how DNA recognition triggers processive plasmid destruction. Our work establishes a mechanistic foundation for how pAgos utilize ancillary factors to achieve plasmid clearance, and provides insights into anti-plasmid immunity in bacteria. }, author = {Bravo, Jack Peter Kelly and Ramos, Delisa A. and Fregoso Ocampo, Rodrigo and Ingram, Caiden and Taylor, David W.}, issn = {1476-4687}, journal = {Nature}, number = {8018}, pages = {961--967}, publisher = {Springer Nature}, title = {{Plasmid targeting and destruction by the DdmDE bacterial defence system}}, doi = {10.1038/s41586-024-07515-9}, volume = {630}, year = {2024}, }