|国家预印本平台
首页|Block structure in boolean matrices of bounded factorization norm

Block structure in boolean matrices of bounded factorization norm

Block structure in boolean matrices of bounded factorization norm

来源:Arxiv_logoArxiv
英文摘要

A boolean matrix is blocky if its $1$-entries form a collection of 1-monochromatic submatrices that are disjoint in both rows and columns. Blocky matrices are precisely the set of boolean matrices with $γ_2$ factorization norm at most $1$. Building on recent work by Balla, Hambardzumyan, and Tomon, we show that for any boolean matrix with $γ_2$ norm at most $λ$, there exists a a collection of row- and column-disjoint 1-monochromatic submatrices that together cover a significant portion (at least a $1/2^{2^{O(λ)}}$ fraction) of its $1$-entries.

Marcel K. Goh、Hamed Hatami

数学

Marcel K. Goh,Hamed Hatami.Block structure in boolean matrices of bounded factorization norm[EB/OL].(2025-07-15)[2025-07-17].https://arxiv.org/abs/2507.00872.点此复制

评论