论文标题
在常规矩阵的二进制和布尔等级上
On the Binary and Boolean Rank of Regular Matrices
论文作者
论文摘要
如果其所有行和列的数量相同，则据说$ 0,1 $矩阵是常规的。我们证明，对于无限的许多整数$ k $，存在一个正常$ 0,1 $矩阵，其二进制等级$ k $，因此其补充的布尔等级为$ k^{\ widetildeme（\ log k）} $。同等地，矩阵中的矩阵中的矩阵中的矩形可以分区，而其零盖所需的矩形数为$ k^{\wideTildeLeΩ（\ log k）} $。这以强烈的形式解决了铂尔曼的问题（线性代数应用程序，1988年）和Hefner，Henson，Lundgren和Maybee的猜想（恭喜，Numer。，1990）。结果可以看作是Balodis，Ben-David，Gour，Jain和Kothari（Focs，2021）的最新结果的定期类似物，这是由集团与独立集合中的独立设置问题以及（不支持的）Alon-Saks-Saks-Seymour猜想在图理论中的动机。作为生产的常规矩阵的应用，我们为Alon-Saks-Seymour猜想获得了定期的反描述，并证明对于无限的许多整数$ k $，存在一个常规图，上面有biclique分区$ k $ $ k $和色度$ k^{\ wideTildememe（\ log k）} $。
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Ω(\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Ω(\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^{\widetildeΩ(\log k)}$.
