2026-08-15T15:16:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20011 2024-06-06T06:21:16Z ddc:004 open_access

Zarankiewicz’s Problem via ε-t-Nets Keller, Chaya Smorodinsky, Shakhar Zarankiewicz’s Problem ε-t-nets pseudo-discs VC-dimension The classical Zarankiewicz’s problem asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph K_{t,t}. Kővári, Sós and Turán proved an upper bound of O(n^{2-1/t}). Fox et al. obtained an improved bound of O(n^{2-1/d}) for graphs of VC-dimension d (where d < t). Basit, Chernikov, Starchenko, Tao and Tran improved the bound for the case of semilinear graphs. Chan and Har-Peled further improved Basit et al.’s bounds and presented (quasi-)linear upper bounds for several classes of geometrically-defined incidence graphs, including a bound of O(n log log n) for the incidence graph of points and pseudo-discs in the plane. In this paper we present a new approach to Zarankiewicz’s problem, via ε-t-nets - a recently introduced generalization of the classical notion of ε-nets. Using the new approach, we obtain a sharp bound of O(n) for the intersection graph of two families of pseudo-discs, thus both improving and generalizing the result of Chan and Har-Peled from incidence graphs to intersection graphs. We also obtain a short proof of the O(n^{2-1/d}) bound of Fox et al., and show improved bounds for several other classes of geometric intersection graphs, including a sharp O(n {log n}/{log log n}) bound for the intersection graph of two families of axis-parallel rectangles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaya Keller and Shakhar Smorodinsky 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.66 urn:nbn:de:0030-drops-200111 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.66 eng https://creativecommons.org/licenses/by/4.0/legalcode