Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Manitoba

$12,000.00

The search for new designs and new codes

EF 2007-08

Résumé
My proposal is to study various combinatorial configurations.  These are subsets of a fixed source set of size v, where the subsets obey certain conditions.  In particular, one of the conditions that will be studied is that the subsets are all the same size, k , and that every pair of elements from the source set occurs the same number of times, t.  These are called 2-designs. The basic question is how many essentially different (non-isomorphic) designs exist when v,k,t are fixed?  These 2-designs are important in statistical designs, cryptography and coding theory.  We will use symmetries and sub-configurations to construct many pretty and useful designs.  We will also study the relationship between codes and 2-designs.          If we change the condition on the subsets to be that the sets are all of size k and that every p set of the source set must intersect some subset in t or more elements, then we have a lottery scheme.  That is, the subsets, if viewed as lottery ticket choices, are guaranteed to give the holder a ticket of at least t winning numbers.  There is huge interest in the public in Canada and in the world on what the minimum number is for fixed v,k,p,t.  We will be creating tables of these numbers, or at least bounds on these numbers, as finding the absolute minimum is a very difficult problem.  These tables will be appreciated both by researchers and people who play the lotteries.  If we change "t or more elements" to "exactly t elements" in the previous definition, then the configurations we are studying are called splitting sets.  The question here is how small can we make the system of sets and still do all the splitting necessary?  The techniques used to construct splitting sets are entirely different from the ones used to construct lotto designs.   Our results on splitting sets are useful in cryptography and theoretical computer science.     Finally, we will study Latin Squares, another combinatorial configuration, closely related to Sudoku squares.  We will be studying the properties of Latin squares and how best to construct them for their applications in statistics, communications and computer algorithms.
Programme
Discovery Grants Program - Individual
Emplacement
Manitoba, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
3558-2007
Name nom
VanRees, John
Department département
Computer Science
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2007
Award amount
12000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
The search for new designs and new codes
Keyword
NA
Application summary
My proposal is to study various combinatorial configurations.  These are subsets of a fixed source set of size v, where the subsets obey certain conditions.  In particular, one of the conditions that will be studied is that the subsets are all the same size, k , and that every pair of elements from the source set occurs the same number of times, t.  These are called 2-designs. The basic question is how many essentially different (non-isomorphic) designs exist when v,k,t are fixed?  These 2-designs are important in statistical designs, cryptography and coding theory.  We will use symmetries and sub-configurations to construct many pretty and useful designs.  We will also study the relationship between codes and 2-designs.          If we change the condition on the subsets to be that the sets are all of size k and that every p set of the source set must intersect some subset in t or more elements, then we have a lottery scheme.  That is, the subsets, if viewed as lottery ticket choices, are guaranteed to give the holder a ticket of at least t winning numbers.  There is huge interest in the public in Canada and in the world on what the minimum number is for fixed v,k,p,t.  We will be creating tables of these numbers, or at least bounds on these numbers, as finding the absolute minimum is a very difficult problem.  These tables will be appreciated both by researchers and people who play the lotteries.  If we change "t or more elements" to "exactly t elements" in the previous definition, then the configurations we are studying are called splitting sets.  The question here is how small can we make the system of sets and still do all the splitting necessary?  The techniques used to construct splitting sets are entirely different from the ones used to construct lotto designs.   Our results on splitting sets are useful in cryptography and theoretical computer science.     Finally, we will study Latin Squares, another combinatorial configuration, closely related to Sudoku squares.  We will be studying the properties of Latin squares and how best to construct them for their applications in statistics, communications and computer algorithms.