Back to Search
Start Over
On the binary and Boolean rank of regular matrices
- Source :
- Journal of Computer and System Sciences. 134:73-86
- Publication Year :
- 2023
- Publisher :
- Elsevier BV, 2023.
-
Abstract
- 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)}$.<br />Comment: 21 pages
- Subjects :
- 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
Subjects
Details
- ISSN :
- 00220000
- Volume :
- 134
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and System Sciences
- Accession number :
- edsair.doi.dedup.....112d78c1b1baea7558cf33a86394465e