b'@online{ghosal2025engineeringinsightsbicliquepartitions,'b'\nTITLE = {Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices},\nAUTHOR = {Ghosal, Angikar and Karrenbauer, Andreas},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2502.06730},\nEPRINT = {2502.06730},\nEPRINTTYPE = {arXiv},\nYEAR = {2025},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {We investigate structural properties of the binary rank of Kronecker powers<br>of binary matrices, equivalently, the biclique partition numbers of the<br>corresponding bipartite graphs. To this end, we engineer a Column Generation<br>approach to solve linear optimization problems for the fractional biclique<br>partition number of bipartite graphs, specifically examining the Domino graph<br>and its Kronecker powers. We address the challenges posed by the double<br>exponential growth of the number of bicliques in increasing Kronecker powers.<br>We discuss various strategies to generate suitable initial sets of bicliques,<br>including an inductive method for increasing Kronecker powers. We show how to<br>manage the number of active bicliques to improve running time and to stay<br>within memory limits. Our computational results reveal that the fractional<br>binary rank is not multiplicative with respect to the Kronecker product. Hence,<br>there are binary matrices, and bipartite graphs, respectively, such as the<br>Domino, where the asymptotic fractional binary rank is strictly smaller than<br>the fractional binary rank. While we used our algorithm to reduce the upper<br>bound, we formally prove that the fractional biclique cover number is a lower<br>bound, which is at least as good as the widely used isolating (or fooling set)<br>bound. For the Domino, we obtain that the asymptotic fractional binary rank<br>lies in the interval $[2,2.373]$. Since our computational resources are not<br>sufficient to further reduce the upper bound, we encourage further exploration<br>using more substantial computing resources or further mathematical engineering<br>techniques to narrow the gap and advance our understanding of biclique<br>partitions, particularly, to settle the open question whether binary rank and<br>biclique partition number are multiplicative with respect to the Kronecker<br>product.<br>},\n}\n'