Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.00298 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917339897790464 |
|---|---|
| author | Garamvölgyi, Dániel Jackson, Bill Jordán, Tibor Villányi, Soma |
| author_facet | Garamvölgyi, Dániel Jackson, Bill Jordán, Tibor Villányi, Soma |
| contents | 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)/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=\mbox{O}(d^3)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00298 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sufficient conditions for bipartite rigidity, symmetric completability and hyperconnectivity of graphs Garamvölgyi, Dániel Jackson, Bill Jordán, Tibor Villányi, Soma Combinatorics 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)/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=\mbox{O}(d^3)$. |
| title | Sufficient conditions for bipartite rigidity, symmetric completability and hyperconnectivity of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.00298 |