A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing

DOI10.1137/15M1007355zbMath1353.05090arXiv1502.01730OpenAlexW2962915177WikidataQ105584154 ScholiaQ105584154MaRDI QIDQ2956040

János Pach, Andrew Suk, Jacob Fox

Publication date: 16 January 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.01730

zbMATH Keywords

regularity lemmaproperty testingsemialgebraic hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)

Related Items

Structure and regularity for subsets of groups with finite VC-dimension, Ramsey properties of algebraic graphs and hypergraphs, A survey of mass partitions, Nondegenerate spheres in four dimensions, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Minimum degree and the graph removal lemma, Crossing and intersecting families of geometric graphs on point sets, Finite quotients of Bruhat–Tits buildings as geometric expanders, Local-vs-global combinatorics, One-Sided Epsilon-Approximants, The Schur-Erdős problem for semi-algebraic colorings, Regular partitions of gentle graphs, Ramsey-Turán numbers for semi-algebraic graphs, On grids in point-line arrangements in the plane, Unnamed Item, Zarankiewicz's problem for semi-algebraic hypergraphs, A positive fraction mutually avoiding sets theorem, Bounds for Pach's selection theorem and for the minimum solid angle in a simplex, On Grids in Point-Line Arrangements in the Plane, Bounded \(VC\)-dimension implies the Schur-Erdős conjecture, Representation Complexities of SemiAlgebraic Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• A short proof of Gowers' lower bound for the regularity lemma
• Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
• Generalizations of the removal lemma
• The complexity of point configurations
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Cutting hyperplanes for divide-and-conquer
• Lower bounds of tower type for Szemerédi's uniformity lemma
• A positive fraction Erdős-Szekeres theorem
• A Tverberg-type result on multicolored simplices
• A tight lower bound for Szemerédi's regularity lemma
• Bounds for graph regularity and removal lemmas
• On extremal problems of graphs and generalized graphs
• Homogeneous selections from hyperplanes
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Crossing patterns of semi-algebraic sets
• Graph removal lemmas
• Space Crossing Numbers
• Testability and repair of hereditary hypergraph properties
• Property testing and its connection to learning and approximation
• Overlap properties of geometric expanders
• Ramsey-type results for semi-algebraic relations
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Randomized Algorithm for Closest-Point Queries
• An Optimal Algorithm for Checking Regularity
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Density and regularity theorems for semi-algebraic hypergraphs
• Easily Testable Graph Properties
• The counting lemma for regular k‐uniform hypergraphs
• Algorithms in real algebraic geometry
• Crossing patterns of segments