Grant: Discovery Grants Program - Individual
University of Manitoba
$27,000.00
Discrete Methods for Flexible and Rigid Tilings
FY 2023-24
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
Recipient
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
2023
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
Combinatorics
Research subject en
Mathématiques pures
Research subject fr
Combinatoire
Application title
Discrete Methods for Flexible and Rigid Tilings
Keyword
Bond-edge types; DNA self-assembly; Flexible tiles; Graph colorings; Graph decompositions; Rigid tiles; Tile types
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.