Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of British Columbia

$12,000.00

Discrete mathematics

EF 2009-10

Résumé
I propose to continue research in the broad area of Discrete Mathematics with a focus on two areas: Extremal Set Theory and Matchings Extremal Set Theory considers a family of subsets of {1,2,..., m} and, given some property imposed on the family, asks whether you can bound the size of the family. With no property, you get the bound of 2 raised to the power m. If you use the property that every pair of sets in the family intersect, then we get the bound 2 raised to the power m-1. This is easily seen to be true by considering that each subset of {1,2,.., m} can be paired with its complement and at most one of the two sets can be chosen for the family. Some of the properties that I will be considering are called forbidden configurations. Given the elementary nature of the forbidden configuration property, it is expected to find applications of these results. These properties (under the name VC-dimension) have found applications to Learning Theory and Computational Geometry. With Sali, we have developed a beautiful conjecture that suggests what structures inside the forbidden configuration really drive the asymptotic bounds. Given a 2mx2m checkerboard, one can ask whether you can cover it with dominoes; each domino covering two squares. This problem is easy and in fact Kastelyn counted the large number of possible ways to do so (using this for statistical mechanics). Can you disrupt the checkerboard and still find a covering by dominoes? For example you could ask what happens if you delete some squares. Obviously you need to delete an equal number of black and white squares since each domino covers one square of each colour. If you add the simple requirement that the deleted black squares be far apart (at least 4 times square root of m) and the same restriction on the deleted whites then a covering is still possible. Moreover the use of square root of m in the distance is best possible. These problems are best described in graph theory; the coverings are called matchings. Investigations on some sensible graphs are continuing.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
8880-2007
Name nom
Anstee, Richard
Department département
Mathematics
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2007
Award amount
12000
Program id
RGPIN
Program nane 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
3
Nb partie
5
Application title
Discrete mathematics
Keyword
NA
Application summary
I propose to continue research in the broad area of Discrete Mathematics with a focus on two areas: Extremal Set Theory and Matchings Extremal Set Theory considers a family of subsets of {1,2,..., m} and, given some property imposed on the family, asks whether you can bound the size of the family. With no property, you get the bound of 2 raised to the power m. If you use the property that every pair of sets in the family intersect, then we get the bound 2 raised to the power m-1. This is easily seen to be true by considering that each subset of {1,2,.., m} can be paired with its complement and at most one of the two sets can be chosen for the family. Some of the properties that I will be considering are called forbidden configurations. Given the elementary nature of the forbidden configuration property, it is expected to find applications of these results. These properties (under the name VC-dimension) have found applications to Learning Theory and Computational Geometry. With Sali, we have developed a beautiful conjecture that suggests what structures inside the forbidden configuration really drive the asymptotic bounds. Given a 2mx2m checkerboard, one can ask whether you can cover it with dominoes; each domino covering two squares. This problem is easy and in fact Kastelyn counted the large number of possible ways to do so (using this for statistical mechanics). Can you disrupt the checkerboard and still find a covering by dominoes? For example you could ask what happens if you delete some squares. Obviously you need to delete an equal number of black and white squares since each domino covers one square of each colour. If you add the simple requirement that the deleted black squares be far apart (at least 4 times square root of m) and the same restriction on the deleted whites then a covering is still possible. Moreover the use of square root of m in the distance is best possible. These problems are best described in graph theory; the coverings are called matchings. Investigations on some sensible graphs are continuing.