Geodesic
A semi-algebraic version of Zarankiewicz's problem
Journal of the European Mathematical Society, Tome 19 (2017) no. 6, pp. 1785-1810 Cet article a éte moissonné depuis la source EMS Press

Voir la notice de l'article

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)∈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=(P,Q,E) in R2 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)d+1d​+ε+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.
DOI : 10.4171/jems/705
Classification : 05-XX, 52-XX
Keywords: Semi-algebraic graph, extremal graph theory, VC-dimension, polynomial partitioning, incidences 
@article{JEMS_2017_19_6_a3,
     author = {Jacob Fox and J\'anos Pach and Adam Sheffer and Andrew Suk and Joshua Zahl},
     title = {A semi-algebraic version of {Zarankiewicz's} problem},
     journal = {Journal of the European Mathematical Society},
     pages = {1785--1810},
     year = {2017},
     volume = {19},
     number = {6},
     doi = {10.4171/jems/705},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/jems/705/}
}
TY  - JOUR
AU  - Jacob Fox
AU  - János Pach
AU  - Adam Sheffer
AU  - Andrew Suk
AU  - Joshua Zahl
TI  - A semi-algebraic version of Zarankiewicz's problem
JO  - Journal of the European Mathematical Society
PY  - 2017
SP  - 1785
EP  - 1810
VL  - 19
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4171/jems/705/
DO  - 10.4171/jems/705
ID  - JEMS_2017_19_6_a3
ER  - 
%0 Journal Article
%A Jacob Fox
%A János Pach
%A Adam Sheffer
%A Andrew Suk
%A Joshua Zahl
%T A semi-algebraic version of Zarankiewicz's problem
%J Journal of the European Mathematical Society
%D 2017
%P 1785-1810
%V 19
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4171/jems/705/
%R 10.4171/jems/705
%F JEMS_2017_19_6_a3
Jacob Fox; János Pach; Adam Sheffer; Andrew Suk; Joshua Zahl. A semi-algebraic version of Zarankiewicz's problem. Journal of the European Mathematical Society, Tome 19 (2017) no. 6, pp. 1785-1810. doi: 10.4171/jems/705

Cité par Sources :