Sufficient conditions for bipartite rigidity, symmetric completability and hyperconnectivity of graphs

We consider three matroids defined by Kalai in 1985: the symmetric completion matroid ${\mathcal{S}}_d$ on the edge set of a looped complete graph; the hyperconnectivity matroid ${\mathcal{H}}_d$ on the edge set of a complete graph; and the birigidity matroid ${\mathcal{B}}_d$ 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 ${\mathcal{S}}_d$ and ${\mathcal{H}}_d$, our conditions are in terms of the minimum degree of $G$ and are best possible. For ${\mathcal{B}}_d$, 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\times n$ positive semidefinite matrices of rank $d$ are uniquely determined by any subset of their entries which includes at least $(n+d+1)\mathrm{/}2$ entries from each row; almost all $m\times n$ matrices of rank $d$ are uniquely determined by any subset of their entries whose positions define a spanning subgraph of $K_{m,n}$ which is $k_d$-connected, for some constant $k_d=O(d^3)$.