## Abstract

Let M be a random m × n 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 N (n, m) denote the number of left null vectors in {0, 1}^{m} for M (including the zero vector), where addition is mod 2. We take n, m → ∞, with m/n → α > 0, while the weight distribution converges weakly to that of a random variable W on {3, 4, 5,…}. Identifying M with a hypergraph on n vertices, we define the 2-core of M as the terminal state of an iterative algorithm that deletes every row incident to a column of degree 1. We identify two thresholds α^{∗} and (Formula presented), and describe them analytically in terms of the distribution of W. Threshold α^{∗} marks the infimum of values of α at which n^{-1} log E[N (n, m)] converges to a positive limit, while (Formula Presented) marks the infimum of values of α at which there is a 2-core of non-negligible size compared to n having more rows than non-empty columns. We have 1/2 ≤ α^{∗} ≤ (Formula presented) ≤ 1, and typically these inequalities are strict; for example when W = 3 almost surely, α^{∗} ≈ 0.8895 and (formula presented) ≈ 0.9179. for which N(n;m) α for which N (n, m) ≥ 2 in probability lies in [α^{∗}, (Formula presented)] and is conjectured to equal (Formula presented). The random row-weight setting gives rise to interesting new phenomena not present in the case of non-random W that has been the focus of previous work.

Original language | English (US) |
---|---|

Pages (from-to) | 1-36 |

Number of pages | 36 |

Journal | Electronic Journal of Probability |

Volume | 19 |

DOIs | |

State | Published - 2014 |

## Keywords

- Ehrenfest model
- Hypercycle
- Hypergraph core
- Large deviations
- Null vector
- Phase transition
- Random allocation
- Random sparse matrix
- XORSAT

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty