Nondegenerate spheres in four dimensions

DOI10.1007/S00454-021-00366-5MaRDI QIDQ2167310zbMATH OpenOpenAlexWikidataFDO

Authors Thao Do

Publication date 25 August 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

incidence geometrynon-degenerate spheressimilar simplices

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: Non-degeneracy was first defined for hyperplanes by Elekes-T'oth, and later extended to spheres by Apfelbaum-Sharir: given a set $P$ of $m$ points in $mathbb{R}^d$ and some $$, a $(d-1)$-dimensional sphere (or a $(d-1)$-sphere) $S$ in $mathbb{R}^d$ is called $$-nondegenerate with respect to $P$ if $S$ does not contain a proper subsphere $S^{\prime }$ such that $$. Apfelbaum-Sharir found an upper bound for the number of incidences between points and nondegenerate spheres in three dimensions, which was recently used by Zahl to obtain the best known bound for the unit distance problem in three dimensions. In this paper, we show that the number of incidences between $m$ points and $n$ $$-nondegenerate 3-spheres in $mathbb{R}^4$ is $$. As a consequence, we obtain a bound of $O_{varepsilon}(n^{2+4/11+varepsilon})$ on the number of similar triangles formed by $n$ points in $mathbb{R}^4$, an improvement over the previously best known bound $O(n^{2+2/5})$. While proving this, we find it convenient to work with a more general definition of nondegeneracy: a bipartite graph $G=(P,Q)$ is called $$-nondegenerate if $$ for any two distinct vertices $q_1,q_{2}inQ$; here $N(q)$ denotes the set of neighbors of $q$ and $$ is some positive constant less than 1. A $$-nondegenerate graph can have up to $Theta(|P||Q|)$ edges without any restriction, but must have much fewer edges if the graph is semi-algebraic or has bounded VC-dimension. We show that previous results for planes and spheres in three dimensions still hold under this new definition, and so does our new bound for spheres in four dimensions.

Recommendations

• Non-Degenerate Spheres in Three Dimensions
• Incidences with k-non-degenerate sets and their applications
• Incidences between points and circles in three and higher dimensions
• Incidences between points and circles in three and higher dimensions
• An improved bound on the number of point-surface incidences in three dimensions

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• A semi-algebraic version of Zarankiewicz's problem
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Almost tight upper bounds for vertical decompositions in four dimensions
• Applications of incidence bounds in point covering problems
• Breaking the 3/2 Barrier for Unit Distances in Three Dimensions
• Combinatorial complexity bounds for arrangements of curves and spheres
• Counting facets and incidences
• Density and regularity theorems for semi-algebraic hypergraphs
• Distinct distances in three and higher dimensions
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1424290 (Why is no real title available?)
• Incidences of not-too-degenerate hyperplanes
• Intersection reverse sequences and geometric applications.
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• Non-Degenerate Spheres in Three Dimensions
• On the density of families of sets
• On the Erdős distinct distances problem in the plane
• On the Number of Incidences Between Points and Curves
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Ramsey-type results for semi-algebraic relations
• Regularity partitions and the topology of graphons
• Research Problems in Discrete Geometry
• Similar simplices in a d-dimensional point set
• The probabilistic method
• Two theorems on point-flat incidences
• Zarankiewicz's problem for semi-algebraic hypergraphs

Cited in

(2)

• Modified spherical harmonics in four dimensions
• Non-Degenerate Spheres in Three Dimensions

This page was built for publication: Nondegenerate spheres in four dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2167310)