Constructing (0,1)-matrices with large minimal defining sets
Citation
Export citationCavenagh, N. J., & Ramadurai, R. (2018). Constructing (0,1)-matrices with large minimal defining sets. Linear Algebra and Its Applications, 537, 38–47. https://doi.org/10.1016/j.laa.2017.09.022
Permanent Research Commons link: https://hdl.handle.net/10289/12057
Abstract
If D is a partially filled-in (0, 1)-matrix with a unique completion to a (0, 1)-matrix M (with prescribed row and column sums), we say that D is a defining set for M. Let A₂ₘ,ₘbe the set of (0, 1)-matrices of dimensions 2m×2m with uniform row and column sum m. It is shown in (Cavenagh, 2013) that the smallest possible size for a defining set of an element of A₂ₘ,ₘ is precisely m². In this note when m is a power of two we construct an element of A₂ₘ,ₘ which has no defining set of size less than 2m² − o(m²). Given that it is easy to show any A₂ₘ,ₘ has a defining set of size at most 2m², this construction is asymptotically optimal. Our construction is based on a array, defined using linear algebra, in which any subarray has asymptotically the same number of 0’s and 1’s.
Date
2018Type
Publisher
Elsevier
Rights
This is an author’s accepted version of an article published in the journal: Discrete Mathematics. © 2018 Elsevier.