A graph theoretic problem concerning lotteries
by
Alewyn P Burger
UNISA
Coauthors: Werner R Grundlingh, Jan H van Vuuren

Suppose a lottery scheme consists of randomly selecting a winning n-set from a universal m-set, while a player participates in the sheme by purchasing a playing set of any number of preselected n-sets from the universal set and is awarded a prize if k or more numbers in the winning n-set match those of at least one of the player's n-sets in his playing set. The player may wish to construct his playing set in such a way that it will necessarily contain at least one n-set which matches at least k numbers in the winning n-set, no matter which winning n-set is chosen from the universal set. The following lottery problem is considered: What is the smallest possible cardinality of a playing set that will guarantee the player a prize. This number is called the lottery number. Various attempts have been made in the combinatorial literature since the early 1960s to find lottery numbers for realistic lottery schemes. These attempts traditionally involved the construction of bounds to other related combinatorial problems, such as the covering problem, the packing problem and the Turan problem. Instead we introduce the concept of a lottery graph here and demonstrate how standard results from graph domination theory lead to simple bound formulations for the lottery number, which are often at least as good as the best covering, packing and other bounds currently available, and even better than these bounds in many realistic cases. Small lottery numbers are found, while bounds are established for larger (more realistic) numbers.

Date received: April 20, 2001