Asymptotic size of covering arrays: an application of entropy compression

2015/03/31 by Francetić, Nevena, Stevens, Brett · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1503.08876

Abstract

A covering array CA(N; t,k,v) is an N × k array A whose each cell takes a value for a v-set V called an 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) = \rm Θ(log₂ k)~\citegodbole_bounds₁996. In this paper we derive two upper bounds on d(t,v)=\limsup_{k → ∞} (CAN(t,k,v))/(log₂ k) using the algorithmic approach to the Lovász local lemma also known as entropy compression.

Cited by

• Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays

Related

• Upper Bounds for Covering Arrays of Higher Index
• Partial Covering Arrays: Algorithms and Asymptotics
• Upper bounds on the size of covering arrays
• A Semi-Random Construction of Small Covering Arrays
• Covering Array Bounds Using Analytical Techniques