Grant: Discovery Grants Program - Individual
University of Manitoba
$40,000.00
Random graphs and percolation processes
EF 2022-23
Résumé
The topics of this research proposal are random graphs, probabilistic combinatorics, and extremal combinatorics with regard to diffusion or activation processes on graphs. The study of such diffusion processes on graphs is often motivated by real-world phenomena in complex networks or statistical physics including rumour or information-spreading and the dynamics of ferromagnetism. As processes on graphs, they provide theoretical problems of interest in their own right. In these cellular automata, vertices of a graph are in one of two states, 'inactive' or 'active', and state updates occur by a local and homogeneous rule. Generally, these updates are repeated and the initial set of active vertices is said to percolate if all vertices are eventually active. For infinite graphs and for large finite graphs, the central question is the behaviour of a typical initially activated set of a particular density and whether there is a critical threshold for the density of a randomly chosen initially activated set to percolate. Much is known about the critical thresholds for percolation in processes where once activated, a vertex remains so forever. In particular, such critical probabilities for grid graphs, infinite trees, some Cayley graphs, and many models of random graphs and geometric graphs have been studied extensively. Most such results rely heavily on the monotone nature of the processes and on the properties of the underlying graph. I propose to investigate a more general class of problems where either the process is not constrained by monotonicity or those where the graph contains both highly structured and also random parts. Of particular interest are those non-monotone models with update rules for which the configurations witnessing the 'deactivation' of a vertex are fewer in number than those witnessing an activation. In some such cases, the effects of deactivation are local and the aim shall be to show that the model behaves, with high probability, in an 'essentially monotone' fashion. To shed light on the relationship between the structure of these graphs and the growth of the activation processes, I intend to address how small perturbations in the underlying graph change a diffusion process and its critical probability.The planned outcome of this research is the development of tools and of a cohesive theory to study these processes in the greatest generality that can encompass those local update rules in which some vertices can be deactivated and can account for random changes to the underlying graph. In the past, rigorous threshold results for these types of graph processes have been found to differ hugely from those predicted by experiments, indicating a need to have precise results to guarantee a solid understanding of the large-scale behaviour of these activation processes.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Manitoba, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2016-05949
Name nom
Gunderson, Karen
Department département
Mathematics - 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
2022
Competition year année de concours
2016
Award amount
40000
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
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
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Installment
inst:6;7
Partie
2
Nb partie
7
Application title
Random graphs and percolation processes
Application summary
The topics of this research proposal are random graphs, probabilistic combinatorics, and extremal combinatorics with regard to diffusion or activation processes on graphs. The study of such diffusion processes on graphs is often motivated by real-world phenomena in complex networks or statistical physics including rumour or information-spreading and the dynamics of ferromagnetism. As processes on graphs, they provide theoretical problems of interest in their own right. In these cellular automata, vertices of a graph are in one of two states, 'inactive' or 'active', and state updates occur by a local and homogeneous rule. Generally, these updates are repeated and the initial set of active vertices is said to percolate if all vertices are eventually active. For infinite graphs and for large finite graphs, the central question is the behaviour of a typical initially activated set of a particular density and whether there is a critical threshold for the density of a randomly chosen initially activated set to percolate. Much is known about the critical thresholds for percolation in processes where once activated, a vertex remains so forever. In particular, such critical probabilities for grid graphs, infinite trees, some Cayley graphs, and many models of random graphs and geometric graphs have been studied extensively. Most such results rely heavily on the monotone nature of the processes and on the properties of the underlying graph. I propose to investigate a more general class of problems where either the process is not constrained by monotonicity or those where the graph contains both highly structured and also random parts. Of particular interest are those non-monotone models with update rules for which the configurations witnessing the 'deactivation' of a vertex are fewer in number than those witnessing an activation. In some such cases, the effects of deactivation are local and the aim shall be to show that the model behaves, with high probability, in an 'essentially monotone' fashion. To shed light on the relationship between the structure of these graphs and the growth of the activation processes, I intend to address how small perturbations in the underlying graph change a diffusion process and its critical probability.The planned outcome of this research is the development of tools and of a cohesive theory to study these processes in the greatest generality that can encompass those local update rules in which some vertices can be deactivated and can account for random changes to the underlying graph. In the past, rigorous threshold results for these types of graph processes have been found to differ hugely from those predicted by experiments, indicating a need to have precise results to guarantee a solid understanding of the large-scale behaviour of these activation processes.