Asymptotic Size of Covering Arrays: An Application of Entropy Compression. Issue 6 (2nd January 2017) - Francetić, Nevena; Stevens, Brett
Abstract: A covering array CA ( N ; t, k, v ) is an N × k array A such that each cell of A takes a value from a v ‐set V, which is called the alphabet. Moreover, the set V t is contained in the set of rows of every N × t subarray of A . The parameter N is called the size of an array and CAN ( t, k, v ) denotes the smallest N for which a CA ( N ; t, k, v ) exists. It is well known that CAN ( t, k, v ) = Θ ( log 2 k )  [10]. In this paper, we derive two upper bounds on d ( t, v ) = lim sup k → ∞ CAN ( t, k, v ) log 2 k using an algorithmic approach to the Lovász local lemma also known as entropy compression.