Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Manitoba

$15,000.00

Extremal graph theory and Ramsey theory

FY 2020-21

Summary
My proposed research is primarily in two areas of mathematics, Ramsey theory and extremal graph theory. Ramsey theory is an area of combinatorics that was, in a sense, initiated by work in logic and, independently, geometry early in the 20th century. It now includes results from graph theory and number theory. Basically, a typical "Ramsey-type" result says that for many classes of structures (e.g., the natural numbers, or graphs) any large structure has the property that whenever certain substructures are partitioned, "homogeneous" patterns can be found in one part. To give one example, if the natural numbers are partitioned into two sets, then by a theorem due to van der Waerden, there exist arbitrarily long arithmetic progressions in one of the sets. Ramsey theory is now rather well-developed, and has since found application in many fields, from graph theory to geometry. Ramsey type problems have inspired (and contributed to) advanced research in many mathematical fields, including number theory, lattice theory, set theory, topology, theoretical computer science and probability, to name but a few. I intend to concentrate on Ramsey theory in graph theory, and on some interesting connections with numbers, including the primes and additive combinatorics. In mathematics, an area called "graph theory" does not deal with graphs of functions (like parabolas), but instead deals with "networks" consisting of "vertices" (points) and "edges" (connections) between vertices. Modern graphs can be used to model algorithms, job allocations, transportation, computer networks (including the internet), epidemiology, or even social networks. One specialization in graph theory is called "extremal graph theory''. In extremal graph theory, one might ask how "dense" a certain graph must be before a chosen (smaller) graph is guaranteed to appear. For example, if a graph on 100 vertices has more than 2500 edges (about half of the 4950 possible) a triangle is guaranteed to appear. Another central question is to determine which graphs are the densest while still not containing the chosen small graph. Such "extremal graphs" can be used to provide critical examples in complexity, number theory, or geometry. Many results in extremal graph theory arose from questions in combinatorial number theory. For example, in 1938, Erdös asked how many numbers from 1 to n can be chosen whose pairwise products are all different? This was answered by examining certain extremal graphs (that forbid a simple four-cycle graph as a subgraph). On the other hand, certain examples from finite geometries or number theory are used to provide answers to Ramsey-type problems or extremal graph theory problems. One feature of studying in these two areas is that not only does one get to learn (and use) many fantastic results from various areas of mathematics, but results in these two areas also contribute back to so many other fields of research.
Program
Discovery Grants Program - Individual
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2016-05959
Name nom
Gunderson, David
Department département
Mathematics
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2016
Award amount
15000
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
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Extremal graph theory and Ramsey theory
Keyword
NSERC
Application summary
My proposed research is primarily in two areas of mathematics, Ramsey theory and extremal graph theory. Ramsey theory is an area of combinatorics that was, in a sense, initiated by work in logic and, independently, geometry early in the 20th century. It now includes results from graph theory and number theory. Basically, a typical "Ramsey-type" result says that for many classes of structures (e.g., the natural numbers, or graphs) any large structure has the property that whenever certain substructures are partitioned, "homogeneous" patterns can be found in one part. To give one example, if the natural numbers are partitioned into two sets, then by a theorem due to van der Waerden, there exist arbitrarily long arithmetic progressions in one of the sets. Ramsey theory is now rather well-developed, and has since found application in many fields, from graph theory to geometry. Ramsey type problems have inspired (and contributed to) advanced research in many mathematical fields, including number theory, lattice theory, set theory, topology, theoretical computer science and probability, to name but a few. I intend to concentrate on Ramsey theory in graph theory, and on some interesting connections with numbers, including the primes and additive combinatorics. In mathematics, an area called "graph theory" does not deal with graphs of functions (like parabolas), but instead deals with "networks" consisting of "vertices" (points) and "edges" (connections) between vertices. Modern graphs can be used to model algorithms, job allocations, transportation, computer networks (including the internet), epidemiology, or even social networks. One specialization in graph theory is called "extremal graph theory''. In extremal graph theory, one might ask how "dense" a certain graph must be before a chosen (smaller) graph is guaranteed to appear. For example, if a graph on 100 vertices has more than 2500 edges (about half of the 4950 possible) a triangle is guaranteed to appear. Another central question is to determine which graphs are the densest while still not containing the chosen small graph. Such "extremal graphs" can be used to provide critical examples in complexity, number theory, or geometry. Many results in extremal graph theory arose from questions in combinatorial number theory. For example, in 1938, Erdös asked how many numbers from 1 to n can be chosen whose pairwise products are all different? This was answered by examining certain extremal graphs (that forbid a simple four-cycle graph as a subgraph). On the other hand, certain examples from finite geometries or number theory are used to provide answers to Ramsey-type problems or extremal graph theory problems. One feature of studying in these two areas is that not only does one get to learn (and use) many fantastic results from various areas of mathematics, but results in these two areas also contribute back to so many other fields of research.
University of Manitoba - $15,000 Grant (2020-21) | Canada Spends