Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Manitoba

$27,000.00

Discrete Methods for Flexible and Rigid Tilings

FY 2024-25

Summary
This research program addresses theoretical problems in graph theory that are inspired by certain experimental processes where nanostructures are assembled from star-shaped DNA molecules that join together through bonding sites on their arm ends. In this context, a natural mathematical question is: What is the least number of molecule types, or of bonding types, required to build a target structure? Abstractly, the assembled structures are described as graphs and the molecules are modeled as 'tiles', vertices with half-edges labeled by symbols representing the bonding types. Using this setup, over the last decade, the aforementioned problem has been tackled by determining the so-called minimum number of tile types and minimum number of bond-edge types of a target graph. In particular, these two graph invariants have been considered under different conditions, such as whether or not the assembly of graphs with fewer vertices than the target is acceptable. Their computation, however, also depends on the specific combinatorial representation of the tiles themselves. On one hand, 'flexible' tiles are defined by just the multiset of labels appearing on their half-edges. On the other, 'rigid' tiles also record geometric features of the corresponding molecules, like arm lengths and inter-arm angles. The minimum numbers of tile and bond-edge types are novel structural graph invariants interesting in their own right. These invariants have been determined for some families of graphs, including trees, cycles, complete and complete bipartite graphs for flexible tiling, with only a handful of polyhedral skeletons analyzed for rigid tiling. This indicates a need of systematic mathematical studies to find these parameters for an arbitrary graph, especially for rigid tiling. For this reason, my long-term goal is to provide a solid combinatorial theory about the minimum numbers of tile and bond-edge types for both flexible and rigid tilings of graphs, while driving interdisciplinary applications of new tools and results in discrete mathematics. Over the next five years, I will focus on: (i) finding new bounds for the minimum numbers of tile and bond-edge types of an arbitrary graph; (ii) unraveling the interdependence between these parameters; (iii) developing a broadly applicable scheme to compute these quantities for rigid tiling. This work will involve applying classical notions in graph theory, such as colorings, decompositions and operations, as well as exploring methods from rigidity theory. This research program will stimulate collaborations with combinatorial computational geometers and possibly with experimentalists in structural biology. Importantly, this modern branch of combinatorics will be an ideal platform for outreach activities, thus fostering equity, diversity and inclusion at different educational levels by inspiring students in pursuing mathematics studies.
Program
Discovery Grants Program - Individual
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2023-04722
Name nom
Ferrari, Margherita Maria
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
2024
Competition year année de concours
2023
Award amount
27000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Discrete Methods for Flexible and Rigid Tilings
Keywords
tile types; bond-edge types; flexible tiles; rigid tiles; graph colorings; graph decompositions; dna self-assembly
Application summary
This research program addresses theoretical problems in graph theory that are inspired by certain experimental processes where nanostructures are assembled from star-shaped DNA molecules that join together through bonding sites on their arm ends. In this context, a natural mathematical question is: What is the least number of molecule types, or of bonding types, required to build a target structure? Abstractly, the assembled structures are described as graphs and the molecules are modeled as 'tiles', vertices with half-edges labeled by symbols representing the bonding types. Using this setup, over the last decade, the aforementioned problem has been tackled by determining the so-called minimum number of tile types and minimum number of bond-edge types of a target graph. In particular, these two graph invariants have been considered under different conditions, such as whether or not the assembly of graphs with fewer vertices than the target is acceptable. Their computation, however, also depends on the specific combinatorial representation of the tiles themselves. On one hand, 'flexible' tiles are defined by just the multiset of labels appearing on their half-edges. On the other, 'rigid' tiles also record geometric features of the corresponding molecules, like arm lengths and inter-arm angles. The minimum numbers of tile and bond-edge types are novel structural graph invariants interesting in their own right. These invariants have been determined for some families of graphs, including trees, cycles, complete and complete bipartite graphs for flexible tiling, with only a handful of polyhedral skeletons analyzed for rigid tiling. This indicates a need of systematic mathematical studies to find these parameters for an arbitrary graph, especially for rigid tiling. For this reason, my long-term goal is to provide a solid combinatorial theory about the minimum numbers of tile and bond-edge types for both flexible and rigid tilings of graphs, while driving interdisciplinary applications of new tools and results in discrete mathematics. Over the next five years, I will focus on: (i) finding new bounds for the minimum numbers of tile and bond-edge types of an arbitrary graph; (ii) unraveling the interdependence between these parameters; (iii) developing a broadly applicable scheme to compute these quantities for rigid tiling. This work will involve applying classical notions in graph theory, such as colorings, decompositions and operations, as well as exploring methods from rigidity theory. This research program will stimulate collaborations with combinatorial computational geometers and possibly with experimentalists in structural biology. Importantly, this modern branch of combinatorics will be an ideal platform for outreach activities, thus fostering equity, diversity and inclusion at different educational levels by inspiring students in pursuing mathematics studies.