A semi-algebraic version of Zarankiewicz's problem
  • Metaadatok
Tartalom: http://real.mtak.hu/73905/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published

Type = Article
Cím:
A semi-algebraic version of Zarankiewicz's problem
Létrehozó:
Fox, Jacob
Pach, JĂĄnos
Sheffer, Ádåm
Suk, Andrew
Zahl, Joshua
Kiadó:
Springer Verlag (Germany)
Dátum:
2017
Téma:
QA Mathematics / matematika
QA166-QA166.245 Graphs theory / grĂĄfelmĂŠlet
Tartalmi leírás:
A bipartite graph G is semi-algebraic in Rd if its vertices are represented by point sets P; Q Rd and its edges are defined as pairs of points.p; q/2 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 Kk;k-free semi-algebraic bipartite graph G D.P; Q; E/in R2 with P D m and Q D n is at most O.mn/2=3 C m C n/, and this bound is tight. In dimensions d = 3, we show that all such semi-algebraic graphs have at most C.mn/d=.dC1/C" C m C n/edges, where " is an arbitrarily small constant and C D C.d; k; t; "/. This result is a far-reaching generalization of the classical Szemeredi-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 Rd, an improved bound for a d-dimensional variant of the Erdos unit distances? problem, and more. © 2017 European Mathematical Society.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Fox, Jacob and Pach, Jånos and Sheffer, Ádåm and Suk, Andrew and Zahl, Joshua (2017) A semi-algebraic version of Zarankiewicz's problem. JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 19 (6). pp. 1785-1810. ISSN 1435-9855
Kapcsolat:
https://doi.org/10.4171/JEMS/705
MTMT:3311545; doi:10.4171/JEMS/705