A generalization of covering designs and lottery wheels

This question is inspired by a recent problem . A (v,k,t) covering design is a pair (V,B) where V is a set of v points and B is a family of k point subsets (called blocks) such that every t points from V is in at least one common block. The La Jolla covering repository lists (among other things) the best known covering designs (judged by fewest blocks) for many v<100,k25 t8. In this question I am only interested in t=2.

To avoid some trivialities later I’d like to relax the definition and allow blocks to have less than k points. For example B={12345,12678,13458,34567} is an optimal (8,5,2) covering design under the usual definition but under the relaxed definition would not be optimal because the first block can be reduced to 2345 and still leave all pairs covered.

The question raised in the recent problem was to find a minimal family of 5 point blocks from a 50 point set such that each of the \binom{50}{5} 5-point sets has at least one pair in at least one common block. I manage to get it to 42 blocks and Douglas Zare to 37 blocks. The technique was to partition the points into 4 groups, choose a good (v,5,2) covering design for each and pool these blocks. My question is if it is obvious that this is the way to get the best solutions.

update The answer is that at least in this case one can get from 37 blocks to 36 by taking four optimal covering designs on 11,11,11, and 17 points, each with a deficient 3 point block, and then replacing these blocks abc def ghi jkl by abcjk defjl ghikl. I’m revising the question to account for this.

To introduce some ungainly definitions: Let a (v,k,[j,2]) lottery wheel (an LW(v,k,[j,2]) be a pair (V,B) with V a set of v points and B a family of blocks, each with at most k points, so that out of every j points there is at least one pair which is in at least one common block. Call such a design optimal if there is no LW(v,k,[j,2]) with fewer blocks and there is no way to delete a point from a single block and have the reduced design still be an LW(v,k,[j,2]). Also, let a partitioned (v,k,[j,2]) lottery wheel (a PLW(v,k,[j,2])) be an LW(v,k,[j,2]) whose points can be partitioned into j-1 (or less, but at least 2) classes such that for each class

  • Every pair of points from that class is covered by a block and
  • The restriction of the blocks to that class forms an optimal (v_i,k,2) covering design up to possibly merging deficient blocks into a single block (as in the example above)

Alternate description of a PLW(v,k,[j,2]: Take j-1 (or less, but at least 2) disjoint (v_i,k,2) covering designs with a total of v points between them and pool their blocks. One is allowed certain additional steps provided that there are deficient blocks which will permit it: One can replace two deficient blocks by their union if this union has no more than k points. One can also remove a block of k’ points, cover its pairs with a tiny (k’,?,2) covering design and then allocate the blocks of that tiny design among various deficient blocks.

Are there any non-trivial v,k,j so that there is an optimal (v,k,[j,2]) lottery wheel which is not partitioned? Is there any non-trivial v,k,j so that no optimal (v,k,[j,2]) lottery wheel is partitioned?

These questions can also be asked for (v,k,t) with t>2, but I will leave it as t=2 for now.

Terminology note. The name lottery wheel (design) is known (and used for many things) so I’m utilizing it here. The idea (as I’ll distort it) is that some lottery chooses a set J of j numbers out of v. A player can make one or more k number bets. A bet wins if it has at least t members in common with J. A lottery wheel is an assortment of bets which attains some goal. In this case the goal is to be sure of at least one winning bet with no consideration of the odds of winning multiple bets nor of getting more than t correct. I hasten to add that my question is purely in designs with no interest in lotteries. Note too that I allow a bet to have less than k numbers.


Source : Link , Question Author : Aaron Meyerowitz , Answer Author : Community

Leave a Comment