Abstract
The problem of Zarankiewicz asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph \(K_{k,k}\) as a subgraph. A classical theorem due to Kővári, Sós, and Turán says that this number of edges is \(O\left( n^{2 - 1/k}\right) \). An important variant of this problem is the analogous question in bipartite graphs with VC-dimension at most d, where d is a fixed integer such that \(k \ge d \ge 2\). A remarkable result of Fox et al. (J. Eur. Math. Soc. (JEMS) 19:1785–1810, 2017) with multiple applications in incidence geometry shows that, under this additional hypothesis, the number of edges in a bipartite graph on n vertices and with no copy of \(K_{k,k}\) as a subgraph must be \(O\left( n^{2 - 1/d}\right) \). This theorem is sharp when \(k=d=2\), because by design any \(K_{2,2}\)-free graph automatically has VC-dimension at most 2, and there are well-known examples of such graphs with \(\Omega \left( n^{3/2}\right) \) edges. However, it turns out this phenomenon no longer carries through for any larger d. We show the following improved result: the maximum number of edges in bipartite graphs with no copies of \(K_{k,k}\) and VC-dimension at most d is \(o(n^{2-1/d})\), for every \(k \ge d \ge 3\).
Similar content being viewed by others
References
Kővári, T., Sós, V.T., Turán, P.: On a problem of K. Zarankiewicz Colloq. Math. 3, 50–57 (1954)
Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)
Brown, W.G.: On graphs that do not contain a Thomsen graph. Can. Math. Bull. 9, 281–285 (1966)
Ball, S., Pepe, V.: Asymptotic improvements to the lower bound of certain bipartite Turán numbers. Combin. Probab. Comput. 21, 323–329 (2012)
Alon, N., Rónyai, L., Szabó, T.: Norm-graphs: variations and applications. J. Combin. Theor. Ser. B 76, 280–290 (1999)
Bohman, T., Keevash, P.: The early evolution of the H-free process. Invent. Math. 181, 291–336 (2010)
Vapnik, V., Chervonenkis, A.: On the uniform convergence of relative frequencies of events to their probabilities. Theor. Probab. Appl. 16, 264–280 (1971)
Fox, J., Pach, J., Suk, A.: Bounded VC-dimension implies the Schur-Erdos conjecture, Symposium on Computational Geometry (SoCG ‘20). Zurich, Switzerland (2020)
Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (JEMS) 19(6), 1785–1810 (2017)
Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9, 145–158 (1993)
Szemerédi, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica 3, 381–392 (1983)
Haussler, D.: Sphere packing numbers for subsets of the Boolean \(n-\)cube with bounded Vapnik-Chervonenkis dimension. J. Combinat. Theor. Ser. A 69, 217–232 (1995)
Sudakov, B., Tomon, I.: The Turán number of bipartite graphs with no \(K_{t, t}\). Proc. Am. Math. Soc. 148, 2811–2818 (2020)
Nagle, B., Rödl, V., Schacht, M.: The counting lemma for regular k-uniform hypergraphs. Random Struct Algorithms 28, 113–179 (2006)
Gowers, T.: Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. Math. 166, 897–946 (2007)
Ramsey, F.P.: On a problem of formal logic. Proc. London Math. Soc. 30, 264–286 (1930)
Jukna, S.: Extremal Combinatorics: With Applications in Computer Science. Springer Science, Cham (2011)
Conlon, D., Lee, J.: On the extremal number of subdivisions. Int. Math. Res. Not. 12, 9122–9145 (2021)
Fox, J., Pach, J., Suk, A.: Erdős-Hajnal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom. 61, 809–829 (2019)
Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry, 2nd Edition, Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlin (2006)
Erdős, P.: On extremal problems of graphs and generalized graphs. Israel J. Math. 2, 183–190 (1964)
Füredi, Z., Simonovits, M.: The history of degenerate (bipartite) extremal graph problems. In: Erdős Centennial, pp. 169–264. Springer, Berlin (2013)
Funding
Research supported by a fellowship at Trinity College. Research supported by an ETH Zürich Postdoctoral Fellowship 20-1 FEL-35.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Janzer, O., Pohoata, C. On the Zarankiewicz Problem for Graphs with Bounded VC-Dimension. Combinatorica 44, 839–848 (2024). https://doi.org/10.1007/s00493-024-00095-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-024-00095-2