2025/02/25 by István Tomon, Tomon, István · 2 citations
Business, Management and Accounting · Engineering · Mathematics · #Advanced Topology and Set Theory #Business Strategy and Innovation #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2502.18429
openalex publication_date 2025/02/25 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
The γ2-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 γ2(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 γ2-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 ℝd, 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.