1,721,009 research outputs found
Topology of real multi-affine hypersurfaces and a homological stability property
No full textLet R be a real closed field. We prove that the number of semi-algebraically connected components of a real hypersurface in Rn defined by a multi-affine polynomial of degree d is bounded by 2d−1. This bound is sharp and is independent of n (as opposed to the classical bound of d(2d−1)n−1 on the Betti numbers of hypersurfaces defined by arbitrary polynomials of degree d in Rn due to Petrovskiĭ and Oleĭnik, Thom and Milnor). Moreover, we show there exists c>1, such that given a sequence (Bn)n>0 where Bn is a closed ball in Rn of positive radius, there exist hypersurfaces (Vn⊂Rn)n>0 defined by symmetric multi-affine polynomials of degree 4, such that ∑i⩽5bi(Vn∩Bn)>cn, where bi(⋅) denotes the i-th Betti number with rational coefficients. Finally, as an application of the main result of the paper we verify a representational stability conjecture due to Basu and Riener on the cohomology modules of symmetric real algebraic sets for a new and much larger class of symmetric real algebraic sets than known before.Fil: Basu, Saugata. Purdue University; Estados UnidosFil: Perrucci, Daniel Roberto. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentin
Efficient Computation of Reeb Spaces and First Homology Groups
No full textThis thesis studies problems in computational topology through the lens of semi-algebraic geometry. We first give an algorithm for computing a semi-algebraic basis for the first homology group, H1(S, F), with coefficients in a field F, of any given semi-algebraic set S ⊂ Rk defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves s polynomials whose degrees are bounded by d, the complexity of the algorithm is bounded by (sd)k O(1). This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point.We then turn our attention to the Reeb graph, a tool from Morse theory which has recently found use in applied topology due to its ability to track the changes in connectivity of level sets of a function. The roadmap of a set, a construction that arises in semi-algebraic geometry, is a one-dimensional set that encodes information about the connected components of a set. In this thesis, we show that the Reeb graph and, more generally, the Reeb space, of a semi-algebraic set is homeomorphic to a semi-algebraic set, which opens up the algorithmic problem of computing a semi-algebraic description of the Reeb graph. We present an algorithm with singly-exponential complexity that realizes the Reeb graph of a function f : X → Y as a semi-algebraic quotient using the roadmap of X with respect to f
Refined Estimates on the Betti Numbers of Real Algebraic Varieties and Semi-Algebraic Sets
No full textWe prove new bounds on the Betti numbers of real varieties and semi-algebraic sets that have a more refined dependence on the degrees of the polynomials defining them than results known before. Our method also unifies several different types of results under a single framework, such as bounds depending on the total degrees, on multi-degrees, as well as in the case of quadratic and partially quadratic polynomials. In the case of bounded total degree, we obtain a bound on the sum of the Betti numbers with an improved leading coefficient, extending a similar result that bounded only the number of connected components. The bounds we present in the case of partially quadratic polynomials offer a significant improvement over what was previously known, particularly in the case when the description of the set is given by both polynomials with bounded total degree and others that are partially quadratic. We conclude with some useful applications to discrete geometry that follow from our main results. In the applications presented, we note that our method allows us to explicitly see the dependence on the different degrees involved for the first time
Some quantitative results in real algebraic geometry
No full textReal algebraic geometry is the study of semi-algebraic sets, subsets of Rk defined by boolean combinations of polynomial equalities and inequalities. The focus of this thesis is to study quantitative results in real algebraic geometry, primarily upper bounds on the topological complexity of semi-algebraic sets as measured, for example, by their Betti numbers
On the Topology of Symmetric Semialgebraic Sets
No full textThis work strengthens and extends an algorithm for computing Betti numbers of symmetric semialgebraic sets developed by Basu and Riener in [11]. We first adapt a construction of Gabrielov and Vorobjov in [18] for replacing arbitrary definable sets by compact ones to the symmetric case. The original construction provided maps from the homotopy and homology groups of the replacement set to those of the original; we show that for sets symmetric relative to the action of some finite reflection group G, we may construct these maps to be equivariant. This modification to the construction for compact replacement allows us to extend Basu and Riener’s theorem on which submodules appear in the isotypic decomposition of each cohomology space to sets not necessarily closed and bounded. Furthermore, by utilizing this equivariant compact approximation, we may obtain a precise description of the aforementioned decomposition of each cohomology space, and not merely the final dimension of the space, from Basu and Riener’s algorithm.Though our equivariant compact replacement holds for G any finite reflection group, Basu and Riener’s results only consider the case of the action the of symmetric group, sometimes termed type A. As a first step towards generalizing Basu and Riener’s work, we examine the next major class of symmetry: the action of the group of signed permutations (known as type B). We focus our attention on Vandermonde varieties, a key object in Basu and Riener’s proofs. We show that the intersection of a type B Vandermonde variety with a fundamental region of type B symmetry is topologically regular. We also prove a result about the intersection of a type B Vandermonde variety with the walls of this fundamental region, leading to the elimination of factors in a different decomposition of the homology spaces
Applied Topology and Algorithmic Semi-Algebraic Geometry
No full textApplied topology is a rapidly growing discipline aiming at using ideas coming from algebraic topology to solve problems in the real world, including analyzing point cloud data, shape analysis, etc. Semi-algebraic geometry deals with studying properties of semi-algebraic sets that are subsets of Rnand defined in terms of polynomial inequalities. Semi-algebraic sets are ubiquitous in applications in areas such as modeling, motion planning, etc. Developing efficient algorithms for computing topological invariants of semi-algebraic sets is a rich and well-developed field. However, applied topology has thrown up new invariants—such as persistent homology and barcodes—which give us new ways of looking at the topology of semi-algebraic sets. In this thesis, we investigate the interplay between these two areas. We aim to develop new efficient algorithms for computing topological invariants of semialgebraic sets, such as persistent homology, and to develop new mathematical tools to make such algorithms possible
Spectral Approach to Modern Algorithm Design
No full textSpectral Methods have had huge influence of modern algorithm design. For algorithmic problems on graphs, this is done by using a deep connection between random walks and the powers of various natural matrices associated with the graph. The major contribution of this thesis initiates attempts to recover algorithmic results in Graph Minor Theory via spectral methods.We make progress towards this goal by exploring these questions in the Property Testing Model for bounded degree graphs. Our main contributions are• The first result gives an almost query optimal one-sided tester for the property of H-minor-freeness. Benjamini-Schramm-Shapira (STOC 2008) conjectured that for fixed H, this can be done in time O˜( √n). Our algorithm solves this in time n1/2+o(1) which nearly resolves this upto no(1) factors.• BSS also conjectured that in the two-sided model, H-minor-freeness can be tested in time poly(1/ε). We resolve this conjecture in the affirmative.• Lastly, in a previous work on the two-sided-question above, Hassidim-KelnerNguyen-Onak (FOCS 2009) introduced a tool they call partition oracle. They conjectured that partition oracles could be implemented in time poly(1/ε) and gave an implementation which took exp(poly(1/ε)) time. In this work, we resolve this conjecture and produce such an oracle.Additionally, this work also presents an algorithm which can recover a planted 3- coloring in a graph with some random like properties and suggests some future research directions alongside
Relations Encoded in Multiway Arrays
No full textUnlike matrix rank, hypermatrix rank is not lower semi-continuous. As a result, optimal low rank approximations of hypermatrices may not exist. Characterizing hypermatrices without optimal low rank approximations is an important step in implementing algorithms with hypermatrices. The main result of this thesis is an original coordinate-free proof that real 2 by 2 by 2 tensors that are rank three do not have optimal rank two approximations with respect to the Frobenius norm. This result was previously only proved in coordinates. Our coordinate-free proof expands on prior results by developing a proof method that can be generalized more readily to higher dimensional tensor spaces. Our proof has the corollary that the nearest point of a rank three tensor to the second secant set of the Segre variety is a rank three tensor in the tangent space of the Segre variety. The relationship between the contraction maps of a tensor generalizes, in a coordinate-free way, the fundamental relationship between the rows and columns of a matrix to hypermatrices. Our proof method demonstrates geometrically the fundamental relationship between the contraction maps of a tensor. For example, we show that a regular real or complex tensor is tangent to the 2 by 2 by 2 Segre variety if and only if the image of any of its contraction maps is tangent to the 2 by 2 Segre variety
Two Problems in Applied Topology
No full textIn this thesis, we present two main results in applied topology. In our first result, we describe an algorithm for computing a semi-algebraic description of the quotient map of a proper semi-algebraic equivalence relation given as input. The complexity of the algorithm is doubly exponential in terms of the size of the polynomials describing the semi-algebraic set and equivalence relation. In our second result, we use the fact that homology groups of a simplicial complex are isomorphic to the space of harmonic chains of that complex to obtain a representative cycle for each homology class. We then establish stability results on the harmonic chain groups
- …
