Most binary matrices have no small defining set

DOI10.1016/J.DISC.2020.112035MaRDI QIDQ785838zbMATH OpenOpenAlexFDO

Authors Carly Bodkin, Anita Liebenau, Ian M. Wanless

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.01267

zbMATH Keywords

binary matricescritical setdefining setrandom bipartite graph

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Consider a matrix $M$ chosen uniformly at random from a class of $mimesn$ matrices of zeros and ones with prescribed row and column sums. A partially filled matrix $D$ is a $mathitdefining$ $mathitset$ for $M$ if $M$ is the unique member of its class that contains the entries in $D$. The $mathitsize$ of a defining set is the number of filled entries. A $mathitcritical$ $mathitset$ is a defining set for which the removal of any entry stops it being a defining set. For some small fixed $epsilon>0$, we assume that $nlem=o(n^{1+epsilon})$, and that $lambdale1/2$, where $lambda$ 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 $mathcalO(n^{1/2+epsilon})$, and that the column sums do not vary by more than $mathcalO(m^{1/2+epsilon})$. Under these assumptions we show that $M$ almost surely has no defining set of size less than $lambdamn-mathcalO(m^{7/4+epsilon})$. It follows that $M$ almost surely has no critical set of size more than $(1-lambda)mn+mathcalO(m^{7/4+epsilon})$. Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when $lambda=1/2$ and $n=m=2^k$ for an integer $k$.

Recommendations

• Defining sets and critical sets in \((0,1)\)-matrices
• The maximum, supremum, and spectrum for critical set sizes in (0,1)-matrices
• Constructing (0,1)-matrices with large minimal defining sets
• Matrices with prescribed row and column sums
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

Cites work

• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Constructing (0,1)-matrices with large minimal defining sets
• Defining sets and critical sets in \((0,1)\)-matrices
• Probability and Computing
• The maximum, supremum, and spectrum for critical set sizes in (0,1)-matrices

Cited in

(4)

• Constructing (0,1)-matrices with large minimal defining sets
• Density of safe matrices
• Defining sets and critical sets in \((0,1)\)-matrices
• The maximum, supremum, and spectrum for critical set sizes in (0,1)-matrices

This page was built for publication: Most binary matrices have no small defining set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q785838)