Structures and lower bounds for binary covering arrays

DOI10.1016/J.DISC.2012.06.013zbMATH Open1248.05018arXiv1111.0587OpenAlexW2066821750MaRDI QIDQ449145FDOQ449145

Hyun Kwang Kim, Dong Yeol Oh, Soohak Choi

Publication date: 12 September 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A $q$-ary $t$-covering array is an $mimesn$ matrix with entries from $0,1,\mathrm{...},q-1$ with the property that for any $t$ column positions, all $q^t$ possible vectors of length $t$ occur at least once. One wishes to minimize $m$ for given $t$ and $n$, or maximize $n$ for given $t$ and $m$. For $t=2$ and $q=2$, it is completely solved by R'enyi, Katona, and Kleitman and Spencer. They also show that maximal binary 2-covering arrays are uniquely determined. Roux found the lower bound of $m$ for a general $t,n$, and $q$. In this article, we show that $mimesn$ binary 2-covering arrays under some constraints on $m$ and $n$ come from the maximal covering arrays. We also improve the lower bound of Roux for $t=3$ and $q=2$, and show that some binary 3 or 4-covering arrays are uniquely determined.

Full work available at URL: https://arxiv.org/abs/1111.0587

Recommendations

• A survey of binary covering arrays
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Covering arrays and intersecting codes
• Binary consecutive covering arrays
• On the state of strength-three covering arrays

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Ko-Rado+theorem&go=Go Erd��s-Ko-Rado theorem]covering arraysRoux's bound

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of packing and covering (05B40)

Cites Work

• A course in combinatorics.
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Universal classes of hash functions
• Two applications (for search theory and truth functions) of Sperner type theorems
• Families of \(k\)-independent sets
• Oblivious transfers and intersecting codes
• Covering arrays and intersecting codes
• Intersecting codes and independent families
• On Representatives of Subsets
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Covering and radius-covering arrays: constructions and classification
• Lower bounds for transversal covers
• Upper bounds for covering arrays by tabu search.
• A classification of the structures of some Sperner families and superimposed codes
• Title not available (Why is that?)
• Subquadratic zero-knowledge
• Title not available (Why is that?)
• Largest induced subgraphs of the n-cube that contain no 4-cycles

Cited In (8)

• A survey of binary covering arrays
• Binary Covering Arrays and Existentially Closed Graphs
• New covering array numbers
• New optimal covering arrays using an orderly algorithm
• Perfect sets of paths in the full graph of SDN switches
• Disjoint Covers in Replicated Heterogeneous Arrays
• Arrays for combinatorial interaction testing: a review on constructive approaches
• Optimum super-simple mixed covering arrays of type \(a^1 b^{k-1}\)

Uses Software

• AETG

This page was built for publication: Structures and lower bounds for binary covering arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449145)