Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Group

University of Calgary

$11,000.00

Relational Structures and Applications

FY 2015-16

Summary
This research program aims at further understanding the connections between the Fraissé theory of amalgamation classes and homogeneous structures, Ramsey theory, and topological dynamics of automorphism groups, driven toward new applications. We propose to formally join our efforts as a team as part of this program, in particular proposing the following lines of research: Precompact expansions The objective is to determine an optimal expansion of homogeneous structures to obtain a Ramsey class with the expansion property, thus providing the existence and means to describe the universal minimal flows. The approach here is to capture basic structural properties with the help of a minimal number of well chosen predicates, very much related to the work on canonical partitions well known by this team. Oscillation stability The famous distortion problem asked whether the Hilbert sphere is approximately indivisible. The notion of oscillation stability was introduced for topological groups, and it turns out that these concepts are equivalent for homogeneous metric spaces. Several results followed, including the proof of a general result that yields the oscillation stability of the Urysohn sphere. This is a very rich area very much influenced by problems in analysis, but with some unresolved fundamental questions. Overgroups of automorphism groups We have explored various natural overgroups of the automorphism group of the Rado graph, generalizing well known methods for reducts. The surprising results in this work point to further work investigating the corresponding overgroups of the other well known homogeneous structures, work very much related to the study of the hypergraph of copies of countable homogeneous structures providing insight into which maps generalizing graph homeomorphisms preserve the copies. Constraint Recognition There are recent connections involving homogeneous structures, omega-categoricity and constraint satisfaction with applications to complexity problems. We propose to investigate some very natural questions general to the study of reducts of omega-categorical structures and the themes above. Distinguishing number This curious notion is a rough measure of symmetry, and we have conjectured that primitive structures should have a distinguishing number of either 2 or omega. This work appears very much related to similar conjectures within the realm of infinite permutation groups, and we propose to extend the investigation of this parameter for homogeneous structures. Equimorphy This fundamental notion explores conditions when two relational structures embed in the other, arising naturally when one studies the preorder of embeddability on relational structures of a fixed age. The failure of the Cantor-Bernstein theorem for sets in the context of embeddings is key to results that are applied in the study of linear orders, graphs and tournaments. We are using these tools from the study of relational structures, such as the notion of chainability and kernel to make advances in this area which has to date largely been studied only for graphs and trees. C-XY homogeneous structures These generalize the classical homogeneity notion. The classification of the C-HH structures was recently done by D. Lockett, and a team's NSERC USRA has made substantial progress in the finite C-MH case, providing renewed hope for the complete classification of this class in the countable case. Intervals in relational structures We have developed techniques, including the notion of inclusive intervals, interval decomposition and lexicographic products, toward understanding primitive structures and cop-win graphs. We will further investigate notions of critical primitivity in the infinite context.
Program
Discovery Grants Program - Group
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPGP-2014-00062
Name nom
Laflamme, Claude
Department département
Mathematics and Statistics
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2014
Award amount
11000
Program id
RGPGP
Program name en
Discovery Grants Program - Group
Program name fr
Programme de subventions à la découverte - équipe
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
2
Nb partie
5
Application title
Relational Structures and Applications
Keyword
NSERC
Application summary
This research program aims at further understanding the connections between the Fraissé theory of amalgamation classes and homogeneous structures, Ramsey theory, and topological dynamics of automorphism groups, driven toward new applications. We propose to formally join our efforts as a team as part of this program, in particular proposing the following lines of research: Precompact expansions The objective is to determine an optimal expansion of homogeneous structures to obtain a Ramsey class with the expansion property, thus providing the existence and means to describe the universal minimal flows. The approach here is to capture basic structural properties with the help of a minimal number of well chosen predicates, very much related to the work on canonical partitions well known by this team. Oscillation stability The famous distortion problem asked whether the Hilbert sphere is approximately indivisible. The notion of oscillation stability was introduced for topological groups, and it turns out that these concepts are equivalent for homogeneous metric spaces. Several results followed, including the proof of a general result that yields the oscillation stability of the Urysohn sphere. This is a very rich area very much influenced by problems in analysis, but with some unresolved fundamental questions. Overgroups of automorphism groups We have explored various natural overgroups of the automorphism group of the Rado graph, generalizing well known methods for reducts. The surprising results in this work point to further work investigating the corresponding overgroups of the other well known homogeneous structures, work very much related to the study of the hypergraph of copies of countable homogeneous structures providing insight into which maps generalizing graph homeomorphisms preserve the copies. Constraint Recognition There are recent connections involving homogeneous structures, omega-categoricity and constraint satisfaction with applications to complexity problems. We propose to investigate some very natural questions general to the study of reducts of omega-categorical structures and the themes above. Distinguishing number This curious notion is a rough measure of symmetry, and we have conjectured that primitive structures should have a distinguishing number of either 2 or omega. This work appears very much related to similar conjectures within the realm of infinite permutation groups, and we propose to extend the investigation of this parameter for homogeneous structures. Equimorphy This fundamental notion explores conditions when two relational structures embed in the other, arising naturally when one studies the preorder of embeddability on relational structures of a fixed age. The failure of the Cantor-Bernstein theorem for sets in the context of embeddings is key to results that are applied in the study of linear orders, graphs and tournaments. We are using these tools from the study of relational structures, such as the notion of chainability and kernel to make advances in this area which has to date largely been studied only for graphs and trees. C-XY homogeneous structures These generalize the classical homogeneity notion. The classification of the C-HH structures was recently done by D. Lockett, and a team's NSERC USRA has made substantial progress in the finite C-MH case, providing renewed hope for the complete classification of this class in the countable case. Intervals in relational structures We have developed techniques, including the notion of inclusive intervals, interval decomposition and lexicographic products, toward understanding primitive structures and cop-win graphs. We will further investigate notions of critical primitivity in the infinite context.