2025/10/31 by Dániel Garamvölgyi, Garamvölgyi, Dániel, Bill Jackson +5
Computer Science · Engineering · #Interconnection Networks and Systems #Structural Analysis and Optimization #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2511.00298
We consider three matroids defined by Kalai in 1985: the symmetric completion matroid Sd on the edge set of a looped complete graph; the hyperconnectivity matroid Hd on the edge set of a complete graph; and the birigidity matroid Bd on the edge set of a complete bipartite graph. These matroids arise in the study of low rank completion of partially filled symmetric, skew-symmetric and rectangular matrices, respectively. We give sufficient conditions for a graph G to have maximum possible rank in these matroids. For Sd and Hd, our conditions are in terms of the minimum degree of G and are best possible. For Bd, our condition is in terms of the connectivity of G. Our results have several implications for the unique completability of low-rank matrices. In particular, they imply that: almost all sufficiently large n × n positive semidefinite matrices of rank d are uniquely determined by any subset of their entries which includes at least (n + d + 1)/2 entries from each row; almost all m × n matrices of rank d are uniquely determined by any subset of their entries whose positions define a spanning subgraph of Km,n which is kd-connected, for some constant kd=O(d3).