2026-07-23T17:22:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16854 2024-03-06T10:58:30Z ddc:004 open_access

On the Binary and Boolean Rank of Regular Matrices Haviv, Ishay Parnas, Michal Binary rank Boolean rank Regular matrices Non-deterministic communication complexity Biclique partition number Chromatic number 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^Ω̃(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^Ω̃(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öö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^Ω̃(log k). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv and Michal Parnas 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.56 urn:nbn:de:0030-drops-168545 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.56 eng https://creativecommons.org/licenses/by/4.0/legalcode