Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of British Columbia

$11,000.00

Investigations in Extremal Combinatorics and Graph Theory

EF 2017-18

Résumé
My research will follow two main threads: Extremal Combinatorics and Matching Theory. For the first problem area I first describe an elementary extremal set problem. There are 2^m subsets of{1,2,...,m}. How many subsets of {1,2,...,m} can you choose so that every pair of subsets have an non-empty intersection? The answer is 2^(m-1)=1/2 x 2^m. The proof of the upper bound is ingenious: pair up each set with its complement. We can only choose one of the two since a set and its complement don't intersect. We consider related extremal problem bounding the number of sets when we are forbidding a given substructure and get polynomial rather than exponential bounds. This relates to the concept of bounded VC-dimension which is a somewhat coarser measure. VC-dimension has had applications to Learning Theory, transversals in Hypergraphs, and computational geometry. We hope that we can develop bounds for our problems that may find application in a similar way. Consider a mxm black/white checkerboard with m even. There are of course many ways to cover the squares of the checkerboard by dominoes (1x2 pieces). What happens if we delete black squares B' and white squares W'. Can the remaining punctured board be covered by dominoes? We certainly need B' and W' to be of equal size (each domino covers one white and one black square). If we require that the deleted squares B' be at distance at least constant times square root of m (and the same for W') then we can show that the remaining punctured board can be covered by dominoes. Moreover the factor square root of m in the distance is optimal. We have extended this to d-dimensional boards. This is a graph matching problem (dominoes become edges). Interestingly the proof uses a topological argument first used in analysis of digital images and also in percolation theory. We will be pursuing other matching problems along these lines.
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-2013
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
2017
Competition year année de concours
2013
Award amount
11000
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
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
5
Nb partie
5
Application title
Investigations in Extremal Combinatorics and Graph Theory
Keyword
NSERC
Application summary
My research will follow two main threads: Extremal Combinatorics and Matching Theory. For the first problem area I first describe an elementary extremal set problem. There are 2^m subsets of{1,2,...,m}. How many subsets of {1,2,...,m} can you choose so that every pair of subsets have an non-empty intersection? The answer is 2^(m-1)=1/2 x 2^m. The proof of the upper bound is ingenious: pair up each set with its complement. We can only choose one of the two since a set and its complement don't intersect. We consider related extremal problem bounding the number of sets when we are forbidding a given substructure and get polynomial rather than exponential bounds. This relates to the concept of bounded VC-dimension which is a somewhat coarser measure. VC-dimension has had applications to Learning Theory, transversals in Hypergraphs, and computational geometry. We hope that we can develop bounds for our problems that may find application in a similar way. Consider a mxm black/white checkerboard with m even. There are of course many ways to cover the squares of the checkerboard by dominoes (1x2 pieces). What happens if we delete black squares B' and white squares W'. Can the remaining punctured board be covered by dominoes? We certainly need B' and W' to be of equal size (each domino covers one white and one black square). If we require that the deleted squares B' be at distance at least constant times square root of m (and the same for W') then we can show that the remaining punctured board can be covered by dominoes. Moreover the factor square root of m in the distance is optimal. We have extended this to d-dimensional boards. This is a graph matching problem (dominoes become edges). Interestingly the proof uses a topological argument first used in analysis of digital images and also in percolation theory. We will be pursuing other matching problems along these lines.