Research Commons
      • Browse 
        • Communities & Collections
        • Titles
        • Authors
        • By Issue Date
        • Subjects
        • Types
        • Series
      • Help 
        • About
        • Collection Policy
        • OA Mandate Guidelines
        • Guidelines FAQ
        • Contact Us
      • My Account 
        • Sign In
        • Register
      View Item 
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computing and Mathematical Sciences Papers
      • View Item
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computing and Mathematical Sciences Papers
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.

      Constructing (0,1)-matrices with large minimal defining sets

      Cavenagh, Nicholas J.; Ramadurai, Reshma
      Thumbnail
      Files
      zeroonefinal.pdf
      Accepted version, 123.1Kb
      DOI
       10.1016/j.laa.2017.09.022
      Find in your library  
      Citation
      Export citation
      Cavenagh, 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
      2018
      Type
      Journal Article
      Publisher
      Elsevier
      Rights
      This is an author’s accepted version of an article published in the journal: Discrete Mathematics. © 2018 Elsevier.
      Collections
      • Computing and Mathematical Sciences Papers [1452]
      Show full item record  

      Usage

      Downloads, last 12 months
      81
       
       
       

      Usage Statistics

      For this itemFor all of Research Commons

      The University of Waikato - Te Whare Wānanga o WaikatoFeedback and RequestsCopyright and Legal Statement