Show simple item record  

dc.contributor.authorCavenagh, Nicholas J.en_NZ
dc.contributor.authorRamadurai, Reshmaen_NZ
dc.date.accessioned2018-09-03T02:50:23Z
dc.date.available2018-01-15en_NZ
dc.date.available2018-09-03T02:50:23Z
dc.date.issued2018en_NZ
dc.identifier.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.022en
dc.identifier.issn0024-3795en_NZ
dc.identifier.urihttps://hdl.handle.net/10289/12057
dc.description.abstractIf 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.
dc.language.isoenen_NZ
dc.publisherElsevieren_NZ
dc.rightsThis is an author’s accepted version of an article published in the journal: Discrete Mathematics. © 2018 Elsevier.
dc.subjectScience & Technologyen_NZ
dc.subjectPhysical Sciencesen_NZ
dc.subjectMathematics, Applieden_NZ
dc.subjectMathematicsen_NZ
dc.subject(0,1)-matrixen_NZ
dc.subjectDefining seten_NZ
dc.subjectFrequency squareen_NZ
dc.subjectF-squareen_NZ
dc.subjectGale-Ryser Theoremen_NZ
dc.titleConstructing (0,1)-matrices with large minimal defining setsen_NZ
dc.typeJournal Article
dc.identifier.doi10.1016/j.laa.2017.09.022en_NZ
dc.relation.isPartOfLinear Algebra and its Applicationsen_NZ
pubs.begin-page38
pubs.elements-id208494
pubs.end-page47
pubs.publication-statusPublisheden_NZ
pubs.volume537en_NZ
dc.identifier.eissn1873-1856en_NZ


Files in this item

This item appears in the following Collection(s)

Show simple item record