@phdthesis{21021, abstract = {This thesis examines how geometry and topology intersect in the representation, transformation, and analysis of complex shapes. It considers how continuous manifolds relate to their discrete analogues, how topological structures evolve in persistence vineyards, and how tools from topological data analysis can illuminate problems in mathematical physics. Central to this exploration is the question of how structure, both geometric and topological, persists or changes under approximation, sampling, or deformation. The work develops new approaches to skeletal and grid-based representations of surfaces, reveals the full expressive capacity of persistence vineyards, and applies topological methods to the longstanding problem of equilibria in electrostatic fields. These threads braid together into a broader understanding of how topology and geometry inform one another across theory, computation, and application.}, author = {Fillmore, Christopher D}, issn = {2663-337X}, pages = {122}, publisher = {Institute of Science and Technology Austria}, title = {{Braiding geometry and topology to study shapes and data}}, doi = {10.15479/AT-ISTA-21021}, year = {2026}, } @article{21766, abstract = {We provide a new characterisation of the decades old open problem of extending bilipschitz mappings given on a Euclidean separated net. In particular, this allows for the complete positive solution of the open problem in dimension two. Along the way, we develop a set of tools for bilipschitz extensions of mappings between subsets of Euclidean spaces.}, author = {Dymond, Michael and Kaluza, Vojtech}, issn = {2737-114X}, journal = {Annales Fennici Mathematici}, keywords = {Lipschitz, bilipschitz, extension, separated net.}, number = {1}, pages = {237--260}, publisher = {Finnish Mathematical Society}, title = {{Extending bilipschitz mappings between separated nets}}, doi = {10.54330/afm.181562}, volume = {51}, year = {2026}, } @article{21704, abstract = {How functional protein sequences are distributed in sequence space is fundamentally important for evolutionary theory and protein design, particularly if a large diversity of protein functions are hidden in evolutionarily unexplored areas of the sequence space. However, this question is understudied in part because experimental and computational studies use extant sequences as a starting point to study sequence space. Here, we study whether extant sequences are representative of the entire functional sequence space. Across thousands of protein families from vertebrates and bacteria we calculate the dimensionality and the volume of sequence space occupied by extant homologs. We find that the observed dimensionality and volume of extant sequence space are minuscule, many orders of magnitude smaller than what we estimated using a model of protein evolution. Simulating sequence evolution we then quantify the impact of phylogeny, selection, and epistasis on restricting the evolutionary exploration of sequence space. We find that sequence evolution from a single common ancestor, or a single point of origin in sequence space, is by far the largest limiting factor that reduces the dimensionality and volume of extant sequence space. These results indicate that there are vast areas of functional sequence space that have not been explored in evolution because of the excessive restrictions on natural exploration of the protein sequence space imposed by the point of origin effect. We suggest that protein design methods that rely on extant sequences may be limited in their ability to discover truly novel functions.}, author = {Isakova, Lada H. and Streltsova, Elizaveta and Bochkareva, Olga and Vlasov, Peter K. and Kondrashov, Fyodor}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {14}, pages = {e2532018123}, publisher = {National Academy of Sciences}, title = {{Descent from a common ancestor restricts exploration of protein sequence space}}, doi = {10.1073/pnas.2532018123}, volume = {123}, year = {2026}, } @article{21778, abstract = {We prove that every 𝐿-bilipschitz mapping ℤ 2 → ℝ2 canbe extended to a 𝐶(𝐿)-bilipschitz mapping ℝ2 → ℝ2,and we provide a polynomial upper bound for 𝐶(𝐿).Moreover, we extend the result to every separated netin ℝ2 instead of ℤ 2, with the upper bound gaininga polynomial dependence on the separation and netconstants associated to the given separated net. Thisanswers an Oberwolfach question of Navas from 2015and is also a positive solution of the two-dimensionalform of a decades old open (in all dimensions at leasttwo) problem due to Alestalo Trotsenko and Väisälä.}, author = {Dymond, Michael and Kaluza, Vojtech}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {4}, publisher = {Wiley}, title = {{Planar bilipschitz extension from separated nets}}, doi = {10.1112/jlms.70540}, volume = {113}, year = {2026}, } @article{18157, abstract = {Interest in sliding block puzzles dates back to the 15-puzzle, seemingly invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating history of the puzzle). The game consists of fifteen movable square blocks numbered and arranged within a square box, leaving one empty space (see Figure 1). The task at hand is to start from a given configuration of the numbered blocks and reach the desired target configuration, where the only allowed move is to slide a numbered block into an adjacent empty space. This task seemed to be unpredictably either very easy to accomplish, or completely impossible, and the puzzle turned into a worldwide sensation in the spring of 1880. A particularly challenging instance, known as the 13-15-14 puzzle, consisted of initial and target configurations that differed by a single swap (historically this swap involved the blocks labeled 14 and 15). The craze of this puzzle was such that it consistently made newspaper headlines in 1880, with an article in the New York Times lamenting that it was “threatening our free institutions” [23, p. 9]. Various prizes were offered for anyone who could solve this challenge, beginning with a $25 set of teeth and culminating with Sam Loyd’s famous $1,000 cash prize.}, author = {Brunck, Florestan R and Kwan, Matthew Alan}, issn = {0343-6993}, journal = {Mathematical Intelligencer}, pages = {52--65}, publisher = {Springer Nature}, title = {{Books, Hallways, and social butterflies: A note on sliding block puzzles}}, doi = {10.1007/s00283-024-10358-x}, volume = {47}, year = {2025}, } @article{18580, abstract = {Motivated by the study of recurrent orbits and dynamics within a Morse set of a Morse decomposition we introduce the concept of Morse predecomposition of an isolated invariant set within the setting of both combinatorial and classical dynamical systems. While Morse decomposition summarizes solely the gradient part of a dynamical system, the developed generalization extends to the recurrent component as well. In particular, a chain recurrent set, which is indecomposable in terms of Morse decomposition, can be represented more finely in the Morse predecomposition framework. This generalization is achieved by forgoing the poset structure inherent to Morse decomposition and relaxing the notion of connection between Morse sets (elements of Morse decomposition) in favor of what we term ’links’. We prove that a Morse decomposition is a special case of Morse predecomposition indexed by a poset. Additionally, we show how a Morse predecomposition may be condensed back to retrieve a Morse decomposition.}, author = {Lipiński, Michał and Mischaikow, Konstantin and Mrozek, Marian}, issn = {1662-3592}, journal = {Qualitative Theory of Dynamical Systems}, number = {1}, publisher = {Springer Nature}, title = {{Morse predecomposition of an invariant set}}, doi = {10.1007/s12346-024-01144-3}, volume = {24}, year = {2025}, } @article{19848, abstract = {Binding precedents (súmulas vinculantes) constitute a juridical instrument unique to the Brazilian legal system and whose objectives include the protection of the Federal Supreme Court against repetitive demands. Studies of the effectiveness of these instruments in decreasing the Court’s exposure to similar cases, however, indicate that they tend to fail in such a direction, with some of the binding precedents seemingly creating new demands. We empirically assess the legal impact of five binding precedents, 11, 14, 17, 26, and 37, at the highest Court level through their effects on the legal subjects they address. This analysis is only possible through the comparison of the Court’s ruling about the precedents’ themes before they are created, which means that these decisions should be detected through techniques of Similar Case Retrieval, which we tackle from the angle of Case Classification. The contributions of this article are therefore twofold: on the mathematical side, we compare the use of different methods of Natural Language Processing — TF-IDF, LSTM, Longformer, and regex — for Case Classification, whereas on the legal side, we contrast the inefficiency of these binding precedents with a set of hypotheses that may justify their repeated usage. We observe that the TF-IDF models performed slightly better than LSTM and Longformer when compared through common metrics; however, the deep learning models were able to detect certain important legal events that TF-IDF missed. On the legal side, we argue that the reasons for binding precedents to fail in responding to repetitive demand are heterogeneous and case-dependent, making it impossible to single out a specific cause. We identify five main hypotheses, which are found in different combinations in each of the precedents studied.}, author = {Tinarrage, Raphaël and Ennes, Henrique and Resck, Lucas and Gomes, Lucas T. and Ponciano, Jean R. and Poco, Jorge}, issn = {1572-8382}, journal = {Artificial Intelligence and Law}, publisher = {Springer Nature}, title = {{Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification}}, doi = {10.1007/s10506-025-09458-6}, year = {2025}, } @inproceedings{20004, abstract = {A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V. Moreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level). To prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.}, author = {Streltsova, Elizaveta and Wagner, Uli}, booktitle = { 41st International Symposium on Computational Geometry}, isbn = {9783959773706}, issn = {1868-8969}, location = {Kanazawa, Japan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers}}, doi = {10.4230/LIPIcs.SoCG.2025.75}, volume = {332}, year = {2025}, } @article{20407, abstract = {We suggest a new algorithm to estimate representations of compact Lie groups from finite samples of their orbits. Different from other reported techniques, our method allows the retrieval of the precise representation type as a direct sum of irreducible representations. Moreover, the knowledge of the representation type permits the reconstruction of its orbit, which is useful for identifying the Lie group that generates the action, from a finite list of candidates. Our algorithm is general for any compact Lie group, but only instantiations for SO(2), T^d, SU(2), and SO(3) are considered. Theoretical guarantees of robustness in terms of Hausdorff and Wasserstein distances are derived. Our tools are drawn from geometric measure theory, computational geometry, and optimization on matrix manifolds. The algorithm is tested for synthetic data up to dimension 32, as well as real-life applications in image analysis, harmonic analysis, density estimation, equivariant neural networks, chemical conformational spaces, and classical mechanics systems, achieving very accurate results.}, author = {Ennes, Henrique and Tinarrage, Raphaël}, issn = {1615-3383}, journal = {Foundations of Computational Mathematics}, publisher = {Springer Nature}, title = {{LieDetect: Detection of representation orbits of compact Lie groups from point clouds}}, doi = {10.1007/s10208-025-09728-4}, year = {2025}, } @inproceedings{20008, abstract = {We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.}, author = {Avvakumov, Sergey and Filakovský, Marek and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli}, booktitle = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing}, isbn = {9798400715105}, issn = {0737-8017}, location = {Prague, Czechia}, pages = {72--83}, publisher = {Association for Computing Machinery}, title = {{Hardness of 4-colouring G-colourable graphs}}, doi = {10.1145/3717823.3718154}, year = {2025}, } @phdthesis{20339, abstract = {This thesis investigates the interplay between algebraic and topological methods and combinatorial problems, focusing on approximate graph colourings and mass partitioning. The unifying theme throughout the dissertation is the use of continuous maps and symmetry constraints to extract combinatorial insights. We first explore approximate graph colouring problems and more generally promise constraint satisfaction problems. Using tools from equivariant topology in combination with the general theory of polymorphism of a promise constraint satisfaction problem, we establish hardness for specific types of approximations. In the second part, we address mass partitioning problems, where one seeks to divide geometric objects or measures in Euclidean space into parts of equal size using hyperplanes. Employing techniques from topological combinatorics (configuration space/test map setup and Borsuk–Ulam type theorems), we both obtain a new equipartitioning result in the and provide a fast algorithm for computing equipartitioning of point sets in 3D. }, author = {Tasinato, Gianluca}, issn = {2663-337X}, pages = {106}, publisher = {Institute of Science and Technology Austria}, title = {{Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems}}, doi = {10.15479/AT-ISTA-20339}, year = {2025}, } @article{19860, abstract = {An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R^3 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R^3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R^3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R^3 (with prescribed normal direction of one of the planes) in time O(n^7/3). A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).}, author = {Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, publisher = {Springer Nature}, title = {{Eight-partitioning points in 3D, and efficiently too}}, doi = {10.1007/s00454-025-00739-0}, year = {2025}, } @article{13974, abstract = {The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2.}, author = {Fulek, Radoslav and Gärtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {831--848}, publisher = {Springer Nature}, title = {{The crossing Tverberg theorem}}, doi = {10.1007/s00454-023-00532-x}, volume = {72}, year = {2024}, } @article{14660, abstract = {The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set 𝑆⊂ℝ𝑑, then there are at most 2𝑑 points of 𝑆 whose convex hull contains the origin in the interior. Bárány, Katchalski,and Pach proved the following quantitative version of Steinitz’s theorem. Let 𝑄 be a convex polytope in ℝ𝑑 containing the standard Euclidean unit ball 𝐁𝑑. Then there exist at most 2𝑑 vertices of 𝑄 whose convex hull 𝑄′ satisfies 𝑟𝐁𝑑⊂𝑄′ with 𝑟⩾𝑑−2𝑑. They conjectured that 𝑟⩾𝑐𝑑−1∕2 holds with a universal constant 𝑐>0. We prove 𝑟⩾15𝑑2, the first polynomial lower bound on 𝑟. Furthermore, we show that 𝑟 is not greater than 2/√𝑑.}, author = {Ivanov, Grigory and Naszódi, Márton}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {2}, pages = {796--802}, publisher = {London Mathematical Society}, title = {{Quantitative Steinitz theorem: A polynomial bound}}, doi = {10.1112/blms.12965}, volume = {56}, year = {2024}, } @article{18604, abstract = {A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a randomized FPT-time algorithm where the parameter is the number of popular faces.}, author = {De Nooijer, Phoebe and Terziadis, Soeren and Weinberger, Alexandra and Masárová, Zuzana and Mchedlidze, Tamara and Löffler, Maarten and Rote, Günter}, issn = {1526-1719}, journal = {Journal of Graph Algorithms and Applications}, number = {2}, pages = {47--82}, publisher = {Brown University}, title = {{Removing popular faces in curve arrangements}}, doi = {10.7155/jgaa.v28i2.2988}, volume = {28}, year = {2024}, } @article{18617, abstract = {Any complex-valued polynomial on (Rn)k decomposes into an algebraic combination of O(n)-invariant polynomials and harmonic polynomials. This decomposition, separation of variables, is granted to be unique if n≥2k−1. We prove that the condition n≥2k−1 is not only sufficient, but also necessary for uniqueness of the separation. Moreover, we describe the structure of non-uniqueness of the separation in the boundary cases when n=2k−2 and n=2k−3. Formally, we study the kernel of a multiplication map ϕ carrying out separation of variables. We devise a general algorithmic procedure for describing Ker ϕ in the restricted non-stable range k≤n<2k−1. In the full non-stable range n<2k−1, we give formulas for highest weights of generators of the kernel as well as formulas for its Hilbert series. Using the developed methods, we obtain a list of highest weight vectors generating Ker ϕ.}, author = {Beďatš, Daniel}, issn = {0021-8693}, journal = {Journal of Algebra}, pages = {281--304}, publisher = {Elsevier}, title = {{Separation of variables for scalar-valued polynomials in the non-stable range}}, doi = {10.1016/j.jalgebra.2024.04.013}, volume = {651}, year = {2024}, } @inproceedings{18917, abstract = {An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).}, author = {Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, location = {Athens, Greece}, pages = {8:1--8:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Eight-partitioning points in 3D, and efficiently too}}, doi = {10.4230/LIPIcs.SoCG.2024.8}, volume = {293}, year = {2024}, } @inproceedings{14888, abstract = {A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces.}, author = {De Nooijer, Phoebe and Terziadis, Soeren and Weinberger, Alexandra and Masárová, Zuzana and Mchedlidze, Tamara and Löffler, Maarten and Rote, Günter}, booktitle = {31st International Symposium on Graph Drawing and Network Visualization}, isbn = {9783031492747}, issn = {1611-3349}, location = {Isola delle Femmine, Palermo, Italy}, pages = {18--33}, publisher = {Springer Nature}, title = {{Removing popular faces in curve arrangements}}, doi = {10.1007/978-3-031-49275-4_2}, volume = {14466}, year = {2024}, } @inproceedings{15296, abstract = {In this paper we build a constructive algorithm that returns a rectifiable curve that connects two points in a weakly convex set in a Hilbert space. We have proven that this algorithm converges and obtained an estimate on the curve’s length and compare the length of the curve obtained to known results.}, author = {Lopushanski, Mariana and Ivanov, Grigory}, booktitle = {AIP Conference Proceedings}, issn = {1551-7616}, location = {Virtual}, number = {1}, publisher = {AIP Publishing}, title = {{A constructive algorithm for building rectifiable curves in weakly convex sets}}, doi = {10.1063/5.0195908}, volume = {3030}, year = {2024}, } @article{9651, abstract = {We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence.}, author = {Dymond, Michael and Kaluza, Vojtech}, issn = {1572-9168}, journal = {Geometriae Dedicata}, publisher = {Springer Nature}, title = {{Divergence of separated nets with respect to displacement equivalence}}, doi = {10.1007/s10711-023-00862-3}, volume = {218}, year = {2024}, }