Stevens–Meagher uniform covering array conjecture

A covering array CA(N,k,v)\operatorname{CA}(N,k,v) is an array with NN rows, kk columns, and entries from an alphabet of size vv, such that every choice of two columns contains every ordered pair of symbols in at least one row. A covering array is uniform if, in each column, the numbers of occurrences of any two symbols differ by at most 11. Stevens–Meagher's uniformity conjecture. If there exists a covering array CA(N,k,v)\operatorname{CA}(N,k,v), then there also exists a uniform covering array CA(N,k,v)\operatorname{CA}(N,k,v). The conjecture asserts that an optimal covering array can always be chosen uniformly, and was formulated in 2005. The paper notes that it holds for all known optimal covering arrays, while an analogous uniformity conjecture for covering and packing codes has been disproved; the constrained covering-array analogue studied here can nevertheless force non-uniformity.

Sources & referencesView supporting material

Primary source

Brett Stevens, “Non-uniform covering array with symmetric forbidden edge constraints”, arXiv:1901.02479 (2019).

Additional references

2 papers in this index state this conjecture (2019). The statement above is taken from the most recent of them; the others are arXiv:1901.03594.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.