2026-07-23T16:35:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25007 2026-02-09T07:52:47Z ddc:004 open_access

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers Chalermsook, Parinya Orgo, Ly Zarsav, Minoo Bipartite graph classes extremal graph theory geometric intersection graphs Zarankiewicz problem bicliques This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Let Z(n;k) be the maximum number of edges in a bipartite graph with n nodes and is free of a k-by-k biclique. Note that Z(n;k) ∈ Ω(nk) for all "natural" graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that Z(n;k) ≤ 9n(k-1) for graphs of Ferrers dimension three, Z(n;k) ∈ Ω(n k ⋅ (log n)/(log log n)) for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of 2n(k-1) for chordal bipartite graphs and 54n(k-1) for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was Z(n;k) ∈ O(2^{O(k)} n), implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parinya Chalermsook and Ly Orgo and Minoo Zarsav 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.21 urn:nbn:de:0030-drops-250074 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode