Grant: Discovery Grants Program - Individual
University of Victoria
$24,000.00
Combinatorial designs and their generalizations
FY 2017-18
Summary
This research aims to improve our understanding of combinatorial designs and some of their generalizations. In the most basic case, a design on some ground set is a collection of subsets which covers any two distinct elements equally often. This is a familiar idea in many geometric models, since two different points uniquely determine a line. Designs underlie well-known puzzles, such as Sudoku and the prisoners hat problem. More importantly, by their nature designs are useful in information theory (through their connection with error-correcting codes), computer science (software testing, network design) and statistics (experimental design). These applications have placed the focus on finite designs, and the beautiful geometries arising from finite fields (binary sequences, for instance) form a natural starting point. It is possible to extend the basic definition above in a number of ways. In a t-design, any t distinct points are to be contained in the same number of blocks. In a graph decomposition, the edges or connections between pairs are to be partitioned into copies of a given small structure. A further possible extension includes the use of edge colours to model two or more simultaneous relationships. As one toy example, a bridge tournament might require every pair of players to be partners exactly once and opponents exactly twice. Although there are many special constructions known, the general existence question for designs and graph decompositions is notoriously hard. This research is mainly concerned with the challenging and most general cases, and especially in situations where standard methods don't apply. A recent celebrated theorem on existence of designs has brought this topic to the forefront of combinatorial mathematics. Even as this theory is complete for extremely large designs, there is still considerable work to be done. In particular, the reasons why specific designs fail to exist leads to wonderful connections to other areas of mathematics, including algebra, analysis and geometry. In comparison with applied mathematics and other sciences, this research is admittedly a step removed from direct industrial applications. However, offsetting this, it is sufficiently general to have end-use in a wide variety of applications. Moreover, the additional structure that information-based problems impose on designs, codes, or arrays is quite often mathematically natural. In this way, the research is guided closely by its applications.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2017-03891
Name nom
Dukes, Peter
Department département
Mathematics and Statistics - Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
24000
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
Combinatorial designs and their generalizations
Keyword
NSERC
Application summary
This research aims to improve our understanding of combinatorial designs and some of their generalizations. In the most basic case, a design on some ground set is a collection of subsets which covers any two distinct elements equally often. This is a familiar idea in many geometric models, since two different points uniquely determine a line. Designs underlie well-known puzzles, such as Sudoku and the prisoners hat problem. More importantly, by their nature designs are useful in information theory (through their connection with error-correcting codes), computer science (software testing, network design) and statistics (experimental design). These applications have placed the focus on finite designs, and the beautiful geometries arising from finite fields (binary sequences, for instance) form a natural starting point. It is possible to extend the basic definition above in a number of ways. In a t-design, any t distinct points are to be contained in the same number of blocks. In a graph decomposition, the edges or connections between pairs are to be partitioned into copies of a given small structure. A further possible extension includes the use of edge colours to model two or more simultaneous relationships. As one toy example, a bridge tournament might require every pair of players to be partners exactly once and opponents exactly twice. Although there are many special constructions known, the general existence question for designs and graph decompositions is notoriously hard. This research is mainly concerned with the challenging and most general cases, and especially in situations where standard methods don't apply. A recent celebrated theorem on existence of designs has brought this topic to the forefront of combinatorial mathematics. Even as this theory is complete for extremely large designs, there is still considerable work to be done. In particular, the reasons why specific designs fail to exist leads to wonderful connections to other areas of mathematics, including algebra, analysis and geometry. In comparison with applied mathematics and other sciences, this research is admittedly a step removed from direct industrial applications. However, offsetting this, it is sufficiently general to have end-use in a wide variety of applications. Moreover, the additional structure that information-based problems impose on designs, codes, or arrays is quite often mathematically natural. In this way, the research is guided closely by its applications.