Towards a characterisation of lottery set overlapping structures

Alewyn P Burger¹, Werner R Gründlingh² & Jan H van Vuuren³

Abstract

Consider a lottery scheme consisting of randomly selecting a winning t-set from a universal mset, while a player participates in the scheme by purchasing a playing set of any number of nsets from the universal set prior to the draw, and is awarded a prize if k or more elements of the winning t-set occur in at least one of the player’s n-sets (1 <= k <= {n, t} <= m). This is called a k-prize. The player may wish to construct a playing set, called a lottery set, which guarantees the player a k-prize, no matter which winning t-set is chosen from the universal set. The cardinality of a smallest lottery set is called the lottery number and is denoted by L(m, n, t; k). In this paper an exhaustive search technique is employed to characterise minimal lottery sets of cardinality not exceeding six, within the ranges 2 <= k <= 4, k <= t <= 11, k <= n <= 12 and max{n, t} <= m <= 20. In the process 32 new lottery numbers are found, and bounds on a further 31 lottery numbers are improved. We provide a theorem that characterises when a minimal lottery set has cardinality three and we also introduce a new parameter, called the lottery characterisation number, which counts the number of non-isomorphic minimal lottery sets for a set of given parameters m, n, t and k. Values for this parameter are derived theoretically for minimal lottery sets of cardinality not exceeding three, and a number of growth and decomposition properties of this parameter are derived for larger lotteries.

An electronic version of the complete paper may be obtained here: [pdf].

An electronic version of the accompanying characterisation tables may be obtained here: [pdf].

Affiliations