## Abstract

Consider a matrix M chosen uniformly at random from a class of m×n matrices of zeros and ones with prescribed row and column sums. A partially filled matrix D is a defining set for M if M is the unique member of its class that contains the entries in D. The size of a defining set is the number of filled entries. A critical set is a defining set for which the removal of any entry stops it being a defining set. For some small fixed ε>0, we assume that n⩽m=o(n^{1+ε}), and that λ⩽1∕2, where λ is the proportion of entries of M that equal 1. We also assume that the row sums of M do not vary by more than O(n^{1∕2+ε}), and that the column sums do not vary by more than O(m^{1∕2+ε}). Under these assumptions we show that M almost surely has no defining set of size less than λmn−O(m^{7∕4+ε}). It follows that M almost surely has no critical set of size more than (1−λ)mn+O(m^{7∕4+ε}). Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when λ=1∕2 and n=m=2^{k} for an integer k.

Original language | English |
---|---|

Article number | 112035 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 343 |

Issue number | 10 |

DOIs | |

Publication status | Published - Oct 2020 |

## Keywords

- Binary matrices
- Critical set
- Defining set
- Random bipartite graph