Factorization norms and Zarankiewicz problems

The γ₂-norm of Boolean matrices plays an important role in communication complexity and discrepancy theory. In this paper, we study combinatorial properties of this norm, and provide new applications, involving Zarankiewicz type problems. We show that if M is an m× n Boolean matrix such that γ₂(M)<γ and M contains no t× t all-ones submatrix, then M contains Oγ,t(m+n) one entries. In other words, graphs of bounded γ₂-norm are degree bounded. This addresses a conjecture of Hambardzumyan, Hatami, and Hatami for locally sparse matrices. We prove that if G is a Kt,t-free incidence graph of n points and n homothets of a polytope P in Rᵈ, then the average degree of G is Od,P(t(log n)O(d)). This is sharp up the $O(.)$ notations. In particular, we prove a more general result on semilinear graphs, which greatly strengthens the work of Basit, Chernikov, Starchenko, Tao, and Tran.