Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"bootstrap percolation"”.
-
Bootstrap Percolation on Random Geometric Graphs
Bootstrap Percolation is a discrete-time process that models the spread of information or disease across the vertex set of a graph. It was introduced in 1979 by Chalupa, Leith and Reich as a simple model of dynamics of ferromagnetism. We consider the following version of this process:Initially, …
-
Tight Bounds on 3-Neighbor Bootstrap Percolation
… set $A_0$ is \emph{lethal} under $r$-neighbor percolation if there exists a $t$ such that $A_t = V(G)$. For a graph $G$, let $m(G,r)$ be the size of the smallest lethal set in $G$ under $r$-neighbor percolation. The problem of determining $m(G,r)$ has been extensively studied for grids $G$ of …
-
Extremal problems about bootstrap percolation on graphs
Bootstrap percolation is a dynamic process on configurations of two possible states of vertices in a graph. For a given graph and a fixed non-negative integer threshold, some vertices are initially "activated" whilst others are "inactivated". At each step, every inactivated vertex will become …
-
Graph bootstrap percolation and additive combinatorial constructions
… small) graph H and an n-vertex graph G the H-bootstrap process on G is defined to be the sequence of graphs which starts with G and in which each graph is obtained from the previous one by adding every edge that completes a copy of H. This process eventually stabilises. We investigate the …
-
Minimum Conditions for Bootstrap Percolation on the Cubic Graph
Bootstrap percolation is an iterative process on the vertices of a graph. Initially, a proper, non-empty set of vertices is infected, and all other vertices are uninfected. At each iteration, every uninfected vertex with a certain number of infected neighbors becomes infected, and all infected …
-
Investigations in the semi-strong product of graphs and bootstrap percolation
… and domination in the semi-strong product Bootstrap Percolation is a process defined on a graph. We begin with an initial set of infected vertices. In each subsequent round, uninfected vertices become infected if they are adjacent to at least r infected vertices. Once infected, vertices …
-
Erasure Correction for Graph Codes as a Problem of Bootstrap Percolation
… terms this procedure is known as {\em bootstrap percolation} with infection threshold $r$ (it is often called infection spread in graphs). The research presented in this thesis extends earlier works on bootstrap percolation. We determine asymptotics of the critical probability $p_c$ of …
-
Geometry of random spaces : geodesics and susceptibility
… set I of active vertices in V, the r-neighbour bootstrap percolation process, attributed to Chalupa, Leath and Reich, is a cellular automaton that evolves by activating vertices with at least r active neighbours. If all vertices in V are activated eventually, we say that I is contagious. A graph …
-
Four Problems in Probability and Optimization
This thesis studies bootstrap percolation, a problem in probability, as well as several topics in the application of sums of squares to combinatorial optimization. In the chapter on percolation, we bound the critical probability for bootstrap percolation on the Hamming torus, as well as the …
-
Extremal Problems for Graph Homomorphisms and Automata
… the evolution of one particular automaton model, bootstrap percolation. Bootstrap percolation is a monotone model of disease spread for which we study the behavior of fast acting, infecting sets of regions in a hexagonal tiling of the plane. We provide exact fastest infection times for certain …
-
Saturation Problems on Graphs
… specific type of weak saturation known as r-bond bootstrap percolation. In the r-bond bootstrap percolation process on a graph G, we start with a set of initially infected edges of G, and consider all other edges in G to be healthy. At each subsequent step in the process, the infection spreads to …
-
Diffusion in heterogeneous networks
… Specifically,we create a generalization of bootstrap percolation which incorporates any number of societies and an arbitrary weight matrix W. The code was created from the start to be as general as possible and to easily be modified with further complications. With it we simulate and analyze …
-
Problems in Graph Theory With Applications to Topology and Modeling RNA
… In the first project, we explore $r$-neighbor bootstrap percolation on a graph $G$. We establish upper bounds for the number of vertices required to percolate in the case that $r=2$ for particular classes of graphs. In the second project, we study the structure of graphs with independence …
-
Three Problems in Discrete Probability
… excursion. The second problem is a study of bootstrap percolation on the Hamming torus. We give a thorough description of the behavior of this model for finite lattices of all dimensions when the percolation threshold is 2. Lastly we present a problem on jigsaw percolation as a model for …
-
Extremal graph theory via structural analysis
… NP-complete. Furthermore we study the following bootstrap percolation process: given a connected graph G, we infect an initial set A of vertices, and in each step a vertex v becomes infected if at least a p-proportion of its neighbours are infected. A set A which infects the whole graph is called …
-
Two Ramsey-related Problems
… of all trees on k vertices. We apply graph bootstrap percolation on a not necessarily Kt-saturated graph to prove that for all t ≥ 4 and k ≥ max{6, t}, there exists a constant c(t, k) such that, for all n ≥ (t - 1)(k - 1) + 1, if G is a (Kt; Tk)-co-critical graph on n vertices, then e(G) ≥ …
-
Statistics of Epidemics in Networks by Passing Messages
… and thus learning about the whole dynamics of bootstrap percolation, which is a simple model known in statistical physics for exhibiting discontinuous phase transition. As an application, we apply a similar model to financial networks, studying when bankruptcies spread due to the sudden …
-
Modelling and analysis of multi-scale networks
… to its time-dependent activation state. Like in bootstrap percolation, the sum of a node’s neighbours’ activation governs its activation in the following time-step. Unlike in it, the activity of this model is highly non-monotone. Limiting (cycles of) states are examined given random initial …
-
Problems in extremal and probabilistic combinatorics
… 4 we consider the <em>r</em>-<em>neighbour bootstrap process</em> in the hypercube. This process starts with an initial set <em>A</em><sub>0</sub> of <em>infected</em> vertices in a graph <em>G</em> and, at each step of the process, a healthy vertex becomes infected if it has at least …