Block structure in boolean matrices of bounded factorization norm
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908449336459264 |
|---|---|
| author | Goh, Marcel K. Hatami, Hamed |
| author_facet | Goh, Marcel K. Hatami, Hamed |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00872 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Block structure in boolean matrices of bounded factorization norm Goh, Marcel K. Hatami, Hamed Classical Analysis and ODEs 15B36, 47L80, 94D10 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. |
| title | Block structure in boolean matrices of bounded factorization norm |
| topic | Classical Analysis and ODEs 15B36, 47L80, 94D10 |
| url | https://arxiv.org/abs/2507.00872 |