Abstract: Let be a random matrix with binary entries and i.i.d. rows. The weight (i.e., number of ones) of a row has a specified probability distribution, with the row chosen uniformly at random given its weight. Let denote the number of left null vectors in for (including the zero vector), where addition is mod 2. We take , with , while the weight distribution may vary with but converges weakly to a limiting distribution on ; let denote a variable with this limiting distribution. Identifying with a hypergraph on vertices, we define the 2-core of as the terminal state of an iterative algorithm that deletes every row incident to a column of degree 1. We identify two thresholds and , and describe them analytically in terms of the distribution of . Threshold marks the infimum of values of at which converges to a positive limit, while marks the infimum of values of at which there is a 2-core of non-negligible size compared to having more rows than non-empty columns. We have , and typically these inequalities are strict; for example when almost surely, numerics give and (previous work on this model has mainly been concerned with such cases where is non-random). The threshold of values of for which in probability lies in and is conjectured to equal . The random row weight setting gives rise to interesting new phenomena not present in the non-random case that has been the focus of previous work.
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.
