Lotto design tables. (English) Zbl 0997.05023
A \(t\)-\((v,k,\lambda)\) covering design is a collection of \(k\)-element sets, called blocks, out of a \(v\)-set of points such that each \(t\)-subset of points is contained in at least \(\lambda\) blocks. A lotto design is a generalization of a covering design with the requirement that, for some \(p\), every \(p\)-set intersects at least \(\lambda\) blocks (commonly, also in this paper, \(\lambda = 1\)) in \(t\) or more points. If \(p=t\), we have a covering design.
In the current paper, the problem of minimizing the size of a lotto design with given parameters is considered. A few new, general combinatorial bounds are presented and computer algorithms for finding bounds for specific parameters are discussed. Bounds on the smallest possible lotto designs are tabulated for \(2 \leq t \leq 4\), \(t+1 \leq p \leq 10\), \(t+1 \leq k \leq 12\), and \(p+1 \leq v \leq 20\). These extensive tables make up most of the paper.
In the current paper, the problem of minimizing the size of a lotto design with given parameters is considered. A few new, general combinatorial bounds are presented and computer algorithms for finding bounds for specific parameters are discussed. Bounds on the smallest possible lotto designs are tabulated for \(2 \leq t \leq 4\), \(t+1 \leq p \leq 10\), \(t+1 \leq k \leq 12\), and \(p+1 \leq v \leq 20\). These extensive tables make up most of the paper.
Reviewer: Patric R.J.Östergård (Helsinki)
References:
| [1] | A generalized covering problem, PhD Thesis, University of Manitoba, 1978. |
| [2] | Bate, The Journal of Combinatorial Mathematics and Combinatorial Computing 28 pp 15– (1998) |
| [3] | Private Communication. |
| [4] | Boyer, Ars Combinatoria 37 pp 13– (1994) |
| [5] | Some lotto numbers from an extension of Turán’s theorem, Math Center (Amsterdam) Report, 1978. |
| [6] | Brouwer, Math Center Tracts 106 pp 99– (1979) |
| [7] | and The CRC handbook of combinatorial designs, CRC Press, Boca Raton, 1996. · Zbl 0836.00010 · doi:10.1201/9781420049954 |
| [8] | Füredi, J Combin Designs 4 pp 5– (1996) |
| [9] | Gordon, J Combin Designs 3 pp 269– (1995) |
| [10] | WebSite of covering bounds at: http://www.ccrwest.org/cover.html |
| [11] | Hanani, Magyar Tud Acad MatKutató 9 pp 155– (1964) |
| [12] | and Combinatorial algorithms, CRC Press, Boca Raton, 1999. |
| [13] | Some results on lotto designs, PhD Thesis, University of Manitoba, 1999. |
| [14] | WebSite of lotto design bounds at: http://www.cs.umanitoba.ca/?lipakc/lottotables.html |
| [15] | Li, Congressus Numerantium 141 pp 5– (1999) |
| [16] | Li, Utilitas Mathematica 58 pp 45– (2000) |
| [17] | Nurmela, Congressus Numerantium 96 pp 93– (1993) |
| [18] | Schönheim, Pac J Math 14 pp 1405– (1964) · Zbl 0128.24501 · doi:10.2140/pjm.1964.14.1405 |
| [19] | Tur’n, Coll Math 3 pp 19– (1954) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
