A semi-algebraic version of Zarankiewicz's problem
Abstract
A bipartite graph G is semi-algebraic in R^d if its vertices are represented by point sets P,Q ⊂ R^d and its edges are defined as pairs of points (p,q) ∈ P×Q that satisfy a Boolean combination of a fixed number of polynomial equations and inequalities in 2d coordinates. We show that for fixed k, the maximum number of edges in a K_(k,k)-free semi-algebraic bipartite graph G=(P,Q,E) in R^2 with |P|=m and |Q|=n is at most O((mn)^(2/3) + m + n), and this bound is tight. In dimensions d ≥ 3, we show that all such semi-algebraic graphs have at most C((mn)^(dd+1+ϵ) + m + n) edges, where here ϵ is an arbitrarily small constant and C=C(d,k,t,ϵ). This result is a far-reaching generalization of the classical Szemerédi-Trotter incidence theorem. The proof combines tools from several fields: VC-dimension and shatter functions, polynomial partitioning, and Hilbert polynomials. We also present various applications of our theorem. For example, a general point-variety incidence bound in R^d, an improved bound for a d-dimensional variant of the Erdös unit distances problem, and more.
Additional Information
© 2017 EMS Publishing House. Supported by a Packard Fellowship, by NSF CAREER award DMS 1352121, and by an Alfred P. Sloan Fellowship. Supported by Hungarian Science Foundation EuroGIGA Grant OTKA NN 102029, by Swiss National Science Foundation Grants 200020-144531 and 200021-137574. Supported by Grant 338/09 from the Israel Science Fund and by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Supported by an NSF Postdoctoral Fellowship and by Swiss National Science Foundation Grant 200021-137574. Supported by an NSF Postdoctoral Fellowship.Attached Files
Submitted - 1407.5705.pdf
Files
Name | Size | Download all |
---|---|---|
md5:de61eeedae3f9460ba6363dbe10eeb78
|
351.7 kB | Preview Download |
Additional details
- Eprint ID
- 78456
- Resolver ID
- CaltechAUTHORS:20170622-080342513
- David and Lucile Packard Foundation
- DMS-1352121
- NSF
- Alfred P. Sloan Foundation
- NN 102029
- Hungarian Scientific Research Fund (OTKA)
- 200020-144531
- Swiss National Science Foundation (SNSF)
- 200021-137574
- Swiss National Science Foundation (SNSF)
- 338/09
- Israel Science Fund
- Israeli Centers of Research Excellence
- NSF Postdoctoral Fellowship
- Created
-
2017-06-22Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field