2024/11/28 by Peter M. W. Gill, Davies, Sara, Gill, Peter +2
Decision Sciences · Mathematics · #05C35 (Primary) 05C65 (Secondary) #Advanced Mathematical Theories #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Inequalities and Applications #Multi-Criteria Decision Making
paper · pdf · doi:10.48550/arxiv.2411.18842
openalex publication_date 2024/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For positive integers s,t,m and n, the Zarankiewicz number z(m,n;s,t) is the maximum number of edges in a subgraph of Km,n that has no complete bipartite subgraph containing s vertices in the part of size m and t vertices in the part of size n. The best general upper bound on Zarankiewicz numbers is a bound due to Roman that can be viewed as the optimal value of a simple linear program. Here we show that in many cases this bound can be improved by adding additional constraints to this linear program. This allows us to prove new upper bounds on Zarankiewicz numbers for many small parameter sets. We are also able to establish a new family of closed form upper bounds on z(m,n;s,t) that captures much, but not all, of the power of the new constraints. This bound generalises a recent result of Chen, Horsley and Mammoliti that applied only in the case s=2.