TY - JOUR
T1 - Most binary matrices have no small defining set
AU - Bodkin, Carly
AU - Liebenau, Anita
AU - Wanless, Ian M.
PY - 2020/10
Y1 - 2020/10
N2 - 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(n1+ε), 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(n1∕2+ε), and that the column sums do not vary by more than O(m1∕2+ε). Under these assumptions we show that M almost surely has no defining set of size less than λmn−O(m7∕4+ε). It follows that M almost surely has no critical set of size more than (1−λ)mn+O(m7∕4+ε). Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when λ=1∕2 and n=m=2k for an integer k.
AB - 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(n1+ε), 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(n1∕2+ε), and that the column sums do not vary by more than O(m1∕2+ε). Under these assumptions we show that M almost surely has no defining set of size less than λmn−O(m7∕4+ε). It follows that M almost surely has no critical set of size more than (1−λ)mn+O(m7∕4+ε). Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when λ=1∕2 and n=m=2k for an integer k.
KW - Binary matrices
KW - Critical set
KW - Defining set
KW - Random bipartite graph
UR - http://www.scopus.com/inward/record.url?scp=85086870600&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2020.112035
DO - 10.1016/j.disc.2020.112035
M3 - Article
AN - SCOPUS:85086870600
VL - 343
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 10
M1 - 112035
ER -