6
$\begingroup$

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 \lt 100, k\le 25$ $t \le 8$. 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=\lbrace 12345,12678,13458,34567 \rbrace$ 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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I recall a paper that had a link to it from LJCR which was coauthored by Greg Kuperberg and reviewed some existing and some new techniques for generating near-optimal covering designs. I recall that there was some random element in picking the next block that helped improve on existing desogns for certain parameters. Perhaps Greg knows of even more recent developments? Gerhard "Ask Me About System Design" Paseman, 2011.06.09 $\endgroup$
    – Gerhard Paseman
    Jun 9, 2011 at 9:49
  • $\begingroup$ How is a "semi-covering design" different from the standard definition of a lottery wheel or lotto design? Is "semi-covering design" used elsewhere? If not, then I think it would be better to use one of the standard terms. $\endgroup$
    – Douglas Zare
    Jun 9, 2011 at 10:43
  • $\begingroup$ @Douglas You are right and I changed it. I don't really find a standard definition and most stuff is ads. But maybe I am not looking in the right place. $\endgroup$
    – Aaron Meyerowitz
    Jun 9, 2011 at 14:28
  • $\begingroup$ In the comments on my answer to the previous question, chous gave a link to a nonpartitioned $(50,5,2)$-wheel with $36$ blocks. I showed that the best partitioned wheel using the covering designs in the La Jolla covering repository would have $37$ blocks. $\endgroup$
    – Douglas Zare
    Jun 9, 2011 at 19:43
  • $\begingroup$ Aha! Well, see above (or your old answer). It turns out that the answer to my question is no but there still may be something going on. $\endgroup$
    – Aaron Meyerowitz
    Jun 10, 2011 at 5:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.