{"ID":2851289,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.20737","arxiv_id":"2510.20737","title":"On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers","abstract":"This paper considers the \\textit{Zarankiewicz problem} in graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while $Z(n;k) \\leq 9n(k-1)$ for graphs of Ferrers dimension three, $Z(n;k) \\in Ω\\left(n k \\cdot \\frac{\\log n}{\\log \\log n}\\right)$ for Ferrers dimension four graphs (Chan \u0026 Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of $2n(k-1)$ for chordal bigraphs 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) \\in O(2^{O(k)} n)$, implied by the results of Fox \u0026 Pach (2006) and Mustafa \u0026 Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.","short_abstract":"This paper considers the \\textit{Zarankiewicz problem} in graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while $Z(n;k) \\leq 9n(k-1)$ for graphs of Ferrers dimension three, $Z(n;k) \\in...","url_abs":"https://arxiv.org/abs/2510.20737","url_pdf":"https://arxiv.org/pdf/2510.20737v1","authors":"[\"Parinya Chalermsook\",\"Ly Orgo\",\"Minoo Zarsav\"]","published":"2025-10-23T16:56:09Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}