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"”.

  1. 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, …

    nebraska Repository record for Bootstrap Percolation on Random Geometric Graphs (opens in a new tab)

  2. 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 …

    uvic Repository record for Tight Bounds on 3-Neighbor Bootstrap Percolation (opens in a new tab)

  3. 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 …

    manitoba Repository record for Extremal problems about bootstrap percolation on graphs (opens in a new tab)

  4. 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 …

    fu-berlin Repository record for Graph bootstrap percolation and additive combinatorial constructions (opens in a new tab)

  5. 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 …

    texas-state Repository record for Minimum Conditions for Bootstrap Percolation on the Cubic Graph (opens in a new tab)

  6. 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 …

    vcu Repository record for Investigations in the semi-strong product of graphs and bootstrap percolation (opens in a new tab)

  7. 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 …

    maryland Repository record for Erasure Correction for Graph Codes as a Problem of Bootstrap Percolation (opens in a new tab)

  8. 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 …

    ubc Repository record for Geometry of random spaces : geodesics and susceptibility (opens in a new tab) Download PDF for Geometry of random spaces : geodesics and susceptibility (opens in a new tab)

  9. 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 …

    washington Repository record for Four Problems in Probability and Optimization (opens in a new tab)

  10. 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 …

    nebraska Repository record for Extremal Problems for Graph Homomorphisms and Automata (opens in a new tab)

  11. 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 …

    uvic Repository record for Saturation Problems on Graphs (opens in a new tab)

  12. 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 …

    uiuc Repository record for Diffusion in heterogeneous networks (opens in a new tab)

  13. 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 …

    vcu Repository record for Problems in Graph Theory With Applications to Topology and Modeling RNA (opens in a new tab)

  14. 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 …

    washington Repository record for Three Problems in Discrete Probability (opens in a new tab)

  15. 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 …

    birmingham Download PDF for Extremal graph theory via structural analysis (opens in a new tab)

  16. 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) ≥ …

    ucf Repository record for Two Ramsey-related Problems (opens in a new tab)

  17. 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 …

    unm Repository record for Statistics of Epidemics in Networks by Passing Messages (opens in a new tab)

  18. 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 …

    lund Repository record for Modelling and analysis of multi-scale networks (opens in a new tab) Download PDF for Modelling and analysis of multi-scale networks (opens in a new tab)

  19. 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 …

    oxford Repository record for Problems in extremal and probabilistic combinatorics (opens in a new tab)