Covering design

In combinatorial design theory, a covering design, or a (v, k, t)-covering design, is a collection of k-element subsets, called blocks, chosen from a v-element set, such that every t-element subset is contained in at least one block. The minimum number of blocks required is the covering number, denoted ${\displaystyle C(v,k,t)}$. Covering designs generalize the notion of a Steiner system and are dual to the concept of a packing design. They have connections to coding theory, Turán theory, and finite geometry. ^[1]

Definition

Let ${\displaystyle V}$ be a set of ${\displaystyle v}$ elements. A (v, k, t)-covering design is a family ${\displaystyle {\mathcal {B}}}$ of ${\displaystyle k}$-element subsets of ${\displaystyle V}$ (each called a block) such that every ${\displaystyle t}$-element subset of ${\displaystyle V}$ is contained in at least one block in ${\displaystyle {\mathcal {B}}}$. The parameters must satisfy ${\displaystyle v\geq k\geq t\geq 0}$.

The covering number${\displaystyle C(v,k,t)}$ is the smallest possible number of blocks in a ${\displaystyle (v,k,t)}$-covering design. ^[2]

The density of a covering design with ${\displaystyle |{\mathcal {B}}|}$ blocks is the average number of blocks containing a given ${\displaystyle t}$-element subset, equal to ^[1]

${\displaystyle {\frac {|{\mathcal {B}}|\,{\binom {k}{t}}}{\binom {v}{t}}}.}$

The density is always at least 1, and equals 1 if and only if every ${\displaystyle t}$-element subset is covered by exactly one block, which is the defining condition of a Steiner system.

Example

Consider ${\displaystyle v=5}$, ${\displaystyle k=3}$, ${\displaystyle t=2}$. The four blocks

${\displaystyle \{1,2,3\},\;\{1,4,5\},\;\{2,4,5\},\;\{3,4,5\}}$

form a (5, 3, 2)-covering design over ${\displaystyle \{1,2,3,4,5\}}$, since every pair of elements appears in at least one block. This is optimal: each block covers three of the ten possible pairs, but any two distinct 3-element subsets of a 5-element set share at most one pair, so three blocks can cover at most nine pairs. Therefore ${\displaystyle C(5,3,2)=4}$.

Bounds

Lower bounds

The most widely used general lower bound is the Schönheim bound, based on a recursive inequality due to Schönheim (1964): ^[3]

${\displaystyle C(v,k,t)\geq \left\lceil {\frac {v}{k}}\,C(v-1,\,k-1,\,t-1)\right\rceil .}$

This inequality has an intuitive interpretation: the element of a covering that appears in the fewest blocks appears in at most ${\displaystyle \lfloor (k/v)\,C(v,k,t)\rfloor }$ blocks, and removing that element and all other blocks yields a ${\displaystyle (v-1,k-1,t-1)}$-covering. ^[1] Applying the inequality recursively yields the closed-form Schönheim bound:

${\displaystyle C(v,k,t)\geq L(v,k,t)=\left\lceil {\frac {v}{k}}\left\lceil {\frac {v-1}{k-1}}\cdots \left\lceil {\frac {v-t+1}{k-t+1}}\right\rceil \cdots \right\rceil \right\rceil .}$

A bound due to de Caen is sometimes tighter, particularly when ${\displaystyle k}$ and ${\displaystyle t}$ are not too small: ^[4]

${\displaystyle C(v,k,t)\geq {\frac {(t+1)(v-t)}{(k+1)(v-k)}}\cdot {\frac {\binom {v}{t}}{\binom {k}{t}}}.}$

Upper bounds

Rödl (1985) proved that for fixed ${\displaystyle k}$ and ${\displaystyle t}$, there exist coverings whose density approaches 1 as ${\displaystyle v\to \infty }$. This implies that the covering number is asymptotically equal to ${\displaystyle {\tbinom {v}{t}}/{\tbinom {k}{t}}}$, matching the trivial lower bound. ^[5]

A weaker but fully explicit bound, valid for all parameter values, was given by Erdős and Spencer (1974) using the probabilistic method: ^[6]

${\displaystyle C(v,k,t)\leq {\frac {\binom {v}{t}}{\binom {k}{t}}}\left(1+\ln {\tbinom {k}{t}}\right).}$

This bound can be improved by at most a constant factor (at most ${\displaystyle 4\ln 2\approx 2.77}$) asymptotically, as demonstrated by the case ${\displaystyle (v,v-1,\lfloor v/2\rfloor )}$, where the Schönheim lower bound gives density asymptotic to ${\displaystyle v/4}$ while the Erdős–Spencer upper bound gives density asymptotic to ${\displaystyle v\ln 2}$. ^[1]

Construction methods

Several general methods are known for constructing covering designs.

Greedy algorithm

A greedy covering is constructed by the following procedure:

1. Arrange all ${\displaystyle k}$-element subsets of the ${\displaystyle v}$-set in a list.
2. Select the ${\displaystyle k}$-subset that covers the greatest number of currently uncovered ${\displaystyle t}$-subsets (breaking ties by position in the list).
3. Repeat until all ${\displaystyle t}$-subsets are covered.

This approach is analogous to the greedy algorithm of Conway and Sloane for constructing lexicographic codes. ^[7] The list of ${\displaystyle k}$-subsets may be arranged in lexicographic order, colexicographic order, Gray code order, or random order; different orderings can yield coverings of different sizes. The greedy method is completely general (it applies to all valid parameters) and in practice produces quite good results: approximately 42% of the table entries computed by Gordon, Kuperberg, and Patashnik came from greedy coverings. Notably, the Steiner system ${\displaystyle S(24,8,5)}$ arises as a greedy covering under lexicographic order. ^[1]

The main disadvantage is computational cost. For fixed ${\displaystyle k}$ and ${\displaystyle t}$, the algorithm requires time and space ${\displaystyle O(v^{k})}$. ^[1]

Finite geometry coverings

Finite geometries yield very good and often optimal coverings for certain parameter families. ^{[8] [9]}

In the projective geometry ${\displaystyle PG(m,q)}$ over the field ${\displaystyle GF(q)}$, the ${\displaystyle k}$-dimensional subspaces (${\displaystyle k}$-flats) cover every set of ${\displaystyle k+1}$ independent points. Taking the ${\displaystyle (q^{m+1}-1)/(q-1)}$ points as elements and the ${\displaystyle k}$-flats as blocks gives the bound:

${\displaystyle C\!\left({\frac {q^{m+1}-1}{q-1}},\;{\frac {q^{k+1}-1}{q-1}},\;k+1\right)\leq {\binom {m+1}{k+1}}_{q}}$

where ${\displaystyle {\tbinom {n}{k}}_{q}}$ denotes the Gaussian binomial coefficient. Similarly, the affine geometry ${\displaystyle AG(m,q)}$ gives:

${\displaystyle C\!\left(q^{m},\;q^{k},\;k+1\right)\leq q^{m-k}{\tbinom {m}{k}}_{q}.}$

In both cases, equality holds when ${\displaystyle k=m-1}$ or ${\displaystyle k=1}$. The coverings by lines (${\displaystyle k=1}$) are Steiner systems. ^[1]

Induced coverings

An induced covering constructs a smaller ${\displaystyle (v',k',t)}$-covering from a larger ${\displaystyle (v,k,t)}$-covering, where ${\displaystyle v'<v}$ and ${\displaystyle k'<k}$. The procedure is to randomly choose ${\displaystyle v'}$ elements of the ${\displaystyle v}$-set, restrict each block to the chosen elements, and then adjust block sizes: blocks smaller than ${\displaystyle k'}$ are padded with arbitrary elements, while blocks larger than ${\displaystyle k'}$ are replaced by a covering of their elements. The resulting family forms a valid ${\displaystyle (v',k',t)}$-covering. ^[1]

This method tends to work best when ${\displaystyle k'/k\approx v'/v}$, and when a good covering, such as one from a finite geometry, is used as the starting point. ^[1]

Combining smaller coverings

A ${\displaystyle (v_{1}+v_{2},k,t)}$-covering can be assembled from coverings on disjoint sets of sizes ${\displaystyle v_{1}}$ and ${\displaystyle v_{2}}$. For each partition of ${\displaystyle t}$ elements into ${\displaystyle s}$ elements from the first set and ${\displaystyle t-s}$ from the second, one uses a ${\displaystyle (v_{1},\ell ,s)}$-covering and a ${\displaystyle (v_{2},k-\ell ,t-s)}$-covering. Optimizing over ${\displaystyle \ell }$ for each value of ${\displaystyle s}$ yields the bound: ^[1]

${\displaystyle C(v_{1}+v_{2},\,k,\,t)\leq \sum _{s=0}^{t}\min _{\ell }\,C(v_{1},\ell ,s)\cdot C(v_{2},k-\ell ,t-s).}$

The products in this sum can have redundancy, which can be reduced using dynamic programming to combine adjacent terms and produce tighter bounds. This method accounts for approximately 30% of the table entries computed by Gordon, Kuperberg, and Patashnik. ^[1] It includes as special cases a number of elementary constructions, such as:

• ${\displaystyle C(v,k+1,t)\leq C(v,k,t)}$ (adding a random element to each block),
• ${\displaystyle C(v+1,k+1,t)\leq C(v,k,t)}$ (adding a new element to every block),
• ${\displaystyle C(v+1,k,t)\leq C(v,k,t)+C(v,k-1,t-1)}$ (adding a new element to only the blocks of the second covering).

Other methods

• Cyclic coverings: If the target size of a covering is ${\displaystyle v}$, one can choose a single ${\displaystyle k}$-subset and take all ${\displaystyle v-1}$ cyclic shifts. For some parameters, this produces optimal coverings. ^[1]
• Hill-climbing and simulated annealing : Starting from a random collection of blocks and iteratively improving by replacing weak blocks. Nurmela and Östergård used simulated annealing to find many good coverings. ^[10]
• Replication: Replacing each element by ${\displaystyle m}$ copies yields ${\displaystyle C(mv,mk,t)\leq C(v,k,t)}$. ^[1]

Special cases and related structures

Steiner systems

Main article: Steiner system

A Steiner system ${\displaystyle S(t,k,v)}$ is a covering design in which every ${\displaystyle t}$-element subset is contained in exactly one block (equivalently, a covering design of density 1). When a Steiner system exists, it is simultaneously an optimal covering and an optimal packing, and ${\displaystyle C(v,k,t)=L(v,k,t)}$. Steiner systems exist only for certain parameter sets; necessary divisibility conditions must be satisfied, and existence is not guaranteed even when these hold. Projective and affine geometries over finite fields provide infinite families of Steiner systems with ${\displaystyle t=2}$. ^[1]

Turán numbers

Main article: Turán number

The Turán number ${\displaystyle T(n,\ell ,r)}$ is the minimum number of ${\displaystyle r}$-element subsets of an ${\displaystyle n}$-set such that every ${\displaystyle \ell }$-element subset contains at least one of the chosen ${\displaystyle r}$-subsets. By passing to complementary subsets, one obtains the identity ^[1]

${\displaystyle C(v,k,t)=T(v,\,v-t,\,v-k).}$

Although covering numbers and Turán numbers are thus equivalent, they have historically been studied in different parameter ranges: covering problems typically have ${\displaystyle v}$ large relative to ${\displaystyle k}$ and ${\displaystyle t}$, while Turán problems typically have ${\displaystyle n}$ large relative to ${\displaystyle \ell }$ and ${\displaystyle r}$ (corresponding to ${\displaystyle k}$ and ${\displaystyle t}$ close to ${\displaystyle v}$). ^[1]

Turán (1941) determined ${\displaystyle T(n,\ell ,2)}$ exactly for all ${\displaystyle n}$ and ${\displaystyle \ell }$, which implies that ${\displaystyle C(v,v-2,t)=L(v,v-2,t)}$ for all ${\displaystyle v}$ and ${\displaystyle t}$. ^{[11] [12]}

Property B

Main article: Property B

Given a finite set ${\displaystyle X}$, a collection ${\displaystyle C}$ of subsets of ${\displaystyle X}$ has Property B if we can partition ${\displaystyle X}$ into two disjoint subsets ${\displaystyle Y}$ and ${\displaystyle Z}$ such that every set in ${\displaystyle C}$ meets both ${\displaystyle Y}$ and ${\displaystyle Z}$. The smallest number of sets in a collection of sets of size ${\displaystyle n}$ such that ${\displaystyle C}$ does not have Property B is denoted by ${\displaystyle m(n)}$.

The search for such a collection can be restricted to covering designs: for any design without Property B, merging any pair of points not occurring in any common block yields another design without Property B, so any minimal counterexample must cover all pairs of points. ^[13]

Tables of covering numbers

Extensive tables of upper bounds on ${\displaystyle C(v,k,t)}$ have been compiled using combinations of the methods described above. Gordon, Kuperberg, and Patashnik (1995) tabulated bounds for ${\displaystyle v\leq 32}$, ${\displaystyle k\leq 16}$, and ${\displaystyle t\leq 8}$, covering 1631 nontrivial parameter sets, of which approximately 93% were obtained from the constructions in their paper. ^[1] An online, regularly updated repository of the best known covering designs is maintained by Gordon. ^[14]

For ${\displaystyle t=2}$, most known covering numbers are optimal, with the ratio between the best known upper and lower bounds being at most approximately 1.12. This ratio increases with ${\displaystyle t}$: up to about 1.89 for ${\displaystyle t=4}$, 2.98 for ${\displaystyle t=6}$, and 3.72 for ${\displaystyle t=8}$. ^[1]

Small covering numbers ${\displaystyle C(v,k,2)}$

${\displaystyle k\setminus v}$	3	4	5	6	7	8	9	10	11	12	13	14	15	16
3	1	3	4	6	7	11	12	17	19	24	26	33	35	43
4		1	3	3	5	6	8	9	11	12	13	18	19	20
5			1	3	3	4	5	6	7	9	10	12	13	15
6				1	3	3	3	4	6	6	7	7	10	10
7					1	3	3	3	4	5	6	6	7	8
8						1	3	3	3	3	4	5	6	6
9							1	3	3	3	3	4	4	5

The covering numbers ${\displaystyle C(v,3,2)}$ for ${\displaystyle v}$ = 3, 4, 5...:

1, 3, 4, 6, 7, 11, 12, 17, 19, 24, 26, 33, 35, 43, 46, 54, 57, 67... (sequence A011975 in the OEIS )

The covering numbers ${\displaystyle C(v,4,2)}$ for ${\displaystyle v}$ = 4, 5, 6...:

1, 3, 3, 5, 6, 8, 9, 11, 12, 13, 18, 19, 20, 26, 27, 31, 35, 37, 39... (sequence A011976 in the OEIS )

Similar sequences for other parameters exist, but unlike the two above, these have a limited number of known entries. The corresponding OEIS sequences are indexed below:

OEIS sequences for covering numbers ${\displaystyle C(v,k,t)}$

${\displaystyle t\setminus k}$	3	4	5	6	7	8	9
2	A011975	A011976	A011977	A011978
3		A011979	A011980	A011981	A011982
4			A011983	A011984	A011985	A011986
5				A011987	A011988	A011989	A011990
6					A066009
7						A066011
8							A066137

Additionally, OEIS sequences exist for certain families where ${\displaystyle k}$ and ${\displaystyle t}$ are defined relative to ${\displaystyle v}$:

• ${\displaystyle C(v,v-3,v-4)}$ (A066140)
• ${\displaystyle C(v,v-4,v-5)}$ (A066225)

See also

• Block design
• Combinatorial design
• Covering code
• Finite geometry
• Set cover problem
• Steiner system

References

1. Gordon, Daniel M.; Kuperberg, Greg; Patashnik, Oren (1995). "New constructions for covering designs" (PDF). Journal of Combinatorial Designs. 3 (4): 269–284. arXiv: math/9502238 . doi:10.1002/jcd.3180030404.
2. Mills, W. H.; Mullin, R. C. (1992). "Coverings and packings". In Dinitz, Jeffrey H.; Stinson, Douglas R. (eds.). Contemporary Design Theory: A Collection of Surveys. Wiley. pp. 371–399. ISBN   0-471-53141-3.
3. Schönheim, J. (1964). "On coverings". Pacific Journal of Mathematics. 14 (4): 1405–1411. doi: 10.2140/pjm.1964.14.1405 .
4. de Caen, D. (1983). "Extension of a theorem of Moon and Moser on complete subgraphs". Ars Combinatoria. 16: 5–10.
5. Rödl, Vojtěch (1985). "On a packing and covering problem". European Journal of Combinatorics. 5 (1): 69–78. doi:10.1016/S0195-6698(85)80023-8.
6. Erdős, Paul; Spencer, Joel (1974). Probabilistic Methods in Combinatorics (PDF). Academic Press. pp. 74–75. doi:10.1002/net.3230070309.
7. Conway, John H.; Sloane, N. J. A. (1986). "Lexicographic codes: Error-correcting codes from game theory" (PDF). IEEE Transactions on Information Theory. 32 (3): 337–348. doi:10.1109/TIT.1986.1057187.
8. Ray-Chaudhuri, D. K. (1968). "Combinatorial information retrieval systems for files". SIAM Journal on Applied Mathematics. 16 (5): 973–992. doi:10.1137/0116079.
9. Abraham, C. T.; Ghosh, S. P.; Ray-Chaudhuri, D. K. (1968). "File organization schemes based on finite geometries". Information and Control. 12 (2): 143–163. doi:10.1016/S0019-9958(68)90251-9.
10. Nurmela, Kari J.; Östergård, Patric R. J. (1993). "Upper bounds for covering designs by simulated annealing". Congressus Numerantium. 96: 93–111.
11. Turán, Paul (1941). "Eine Extremalaufgabe aus der Graphentheorie". Mat. Fiz. Lapok (in Hungarian). 48: 436–452.
12. de Caen, D. (1994). "The current status of Turán's problem on hypergraphs". In Frankl, P.; Füredi, Z.; Katona, G.; Miklós, D. (eds.). Extremal Problems for Finite Sets. Budapest: János Bolyai Mathematical Society. pp. 187–197. ISBN   9638022817.
13. Östergård, Patric R. J. (30 January 2014). "On the minimum size of 4-uniform hypergraphs without property B". Discrete Applied Mathematics. 163, Part 2: 199–204. doi: 10.1016/j.dam.2011.11.035 .
14. Gordon, Daniel M. "La Jolla Covering Repository".

External links

• La Jolla Covering Repository, tables of best known covering designs, maintained by Daniel M. Gordon