Rank deficiency in sparse random \(\mathrm{GF}[2]\) matrices (Q743514)

For each fixed \(n\) the authors sample \(m_{n}\) independently but identically distributed random vectors whose entries are \(0\)'s and \(1\)'s. The random vectors where the sampling is made from, come from random variables \(W\in \{1,2,\ldots\}\), and a sequence \(W_{n}\) that converges in probability to \(W\). The authors argue that such scheme is motivated from various applications that they describe. They analyze the quantity \(\mathcal{N}_{n}=2^{\sigma(n,m_{n})}\), where \(\sigma(n,m_{n})=m-k\) and \(k\) is the dimension of the subspace generated by the previously mentioned \(m_{n}\) vectors. In particular, when \(m_{n}/n\to \alpha\), they give an explicit formula, in terms of \(\rho(s)=E[s^{W}]\), of some asymptotics for the expectation of \(\mathcal{N}_{n}\). Moreover, using \(\rho\) again, they also give a threshold for \(\alpha\), where more information about \(\mathcal{N}_{n}\) is given in the limit. In their proofs, the authors make use of the concept of hypergraphs, which is a generalization of a graph, namely where \(3\) or more edges are associated to a set called hyperedge.