|ZOLTAN FÜREDI, University of Illinois at Urbana, Urbana, Illinois 61801-2975, USA|
|Lotto, footballpool and other covering radius problems|
The aim of this talk is to review connections between Turán's (hyper)graph problem and other parts of Combinatorics, like Steiner systems, packings and coverings, constant weight codes, Kneser graphs.
The code C is called a covering code of X with radius rif every element of X is within Hamming distance r from at least one codeword from C. Given X we are interested in a minimum sized C. Continuing a work of Hanani, Ornstein and Sós, and Brouwer we determine the Lottery number, L(n,k,p,2), the minimum number of k-subsets of an n-set such that all the p-sets are intersected by one of them in at least 2 elements, for all n> n0(k,p). Answering a question of Hämäläinen, Honkala, Litsyn and Östergard we show further connections between Turán theorem and constant weight covering codes.