On the binary and Boolean rank of regular matrices
| Autor: | Haviv, Ishay, Parnas, Michal |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Theory of computation → Communication complexity Discrete Mathematics (cs.DM) Non-deterministic communication complexity General Computer Science Computer Networks and Communications Applied Mathematics Regular matrices Biclique partition number Chromatic number Computational Complexity (cs.CC) Boolean rank Theoretical Computer Science Computer Science - Computational Complexity Computational Theory and Mathematics Computer Science::Discrete Mathematics FOS: Mathematics Mathematics of computing → Graph coloring Mathematics - Combinatorics Combinatorics (math.CO) Binary rank Computer Science - Discrete Mathematics |
| Zdroj: | Journal of Computer and System Sciences. 134:73-86 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2023.01.005 |
| Popis: | A $0,1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$, there exists a square regular $0,1$ matrix with binary rank $k$, such that the Boolean rank of its complement is $k^{\widetilde{\Omega}(\log k)}$. Equivalently, the ones in the matrix can be partitioned into $k$ combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is $k^{\widetilde{\Omega}(\log k)}$. This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, G\"{o}\"{o}s, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers $k$, there exists a regular graph with biclique partition number $k$ and chromatic number $k^{\widetilde{\Omega}(\log k)}$. Comment: 21 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect