Purdue University Graduate School
A_thesis.pdf (1.15 MB)

Betti numbers of deterministic and random sets in semi-algebraic and o-minimal geometry

Download (1.15 MB)
posted on 2020-05-06, 18:10 authored by Abhiram NatarajanAbhiram Natarajan

Studying properties of random polynomials has marked a shift in algebraic geometry. Instead of worst-case analysis, which often leads to overly pessimistic perspectives, randomness helps perform average-case analysis, and thus obtain a more realistic view. Also, via Erdos' astonishing 'probabilistic method', one can potentially obtain deterministic results by introducing randomness into a question that apriori had nothing to do with randomness.

In this thesis, we study topological questions in real algebraic geometry, o-minimal geometry and random algebraic geometry, with motivation from incidence combinatorics. Specifically, we prove results along two different threads:

1. Topology of semi-algebraic and definable (over any o-minimal structure over R) sets, in both deterministic and random settings.

2. Topology of random hypersurface arrangements. In this case, we also prove a result that could be of independent interest in random graph theory.

Towards the first thread, motivated by applications in o-minimal incidence combinatorics, we prove bounds (both deterministic and random) on the topological complexity (as measured by the Betti numbers) of general definable hypersurfaces restricted to algebraic sets. Given any sequence of hypersurfaces, we show that there exists a definable hypersurface G, and a sequence of polynomials, such that each manifold in the sequence of hypersurfaces appears as a component of G restricted to the zero set of some polynomial in the sequence of polynomials. This shows that the topology of the intersection of a definable hypersurface and an algebraic set can be made arbitrarily pathological. On the other hand, we show that for random polynomials, the Betti numbers of the restriction of the zero set of a random polynomial to any definable set deviates from a Bezout-type bound with bounded probability.

Progress in o-minimal incidence combinatorics has lagged behind the developments in incidence combinatorics in the algebraic case due to the absence of an o-minimal version of the Guth-Katz polynomial partitioning theorem, and the first part of our work explains why this is so difficult. However, our average result shows that if we can prove that the measure of the set of polynomials which satisfy a certain property necessary for polynomial partitioning is suitably bounded from below, by the probabilistic method, we get an o-minimal polynomial partitioning theorem. This would be a tremendous breakthrough and would enable progress on multiple fronts in model theoretic combinatorics.

Along the second thread, we have studied the average Betti numbers of random hypersurface arrangements. Specifically, we study how the average Betti numbers of a finite arrangement of random hypersurfaces grows in terms of the degrees of the polynomials in the arrangement, as well as the number of polynomials. This is proved using a random Mayer-Vietoris spectral sequence argument. We supplement this result with a better bound on the average Betti numbers when one considers an arrangement of quadrics. This question turns out to be equivalent to studying the expected number of connected components of a certain random graph model, which has not been studied before, and thus could be of independent interest. While our motivation once again was incidence combinatorics, we obtained the first bounds on the topology of arrangements of random hypersurfaces, with an unexpected bonus of a result in random graphs.


AF: Small: Symmetry, Randomness and Computations in Real Algebraic Geometry

Directorate for Computer & Information Science & Engineering

Find out more...

AF: Small: Quantitative and Algorithmic Aspects of Semi-algebraic Sets and Partitions

Directorate for Computer & Information Science & Engineering

Find out more...

Purdue Research Foundation Grant


Degree Type

  • Doctor of Philosophy


  • Computer Science

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Prof. Saugata Basu

Advisor/Supervisor/Committee co-chair

Prof. Elena Grigorescu

Additional Committee Member 2

Prof. Hemanta Maji

Additional Committee Member 3

Prof. Simina Branzei