{
"id": "1909.04649",
"version": "v1",
"published": "2019-09-10T17:49:09.000Z",
"updated": "2019-09-10T17:49:09.000Z",
"title": "Bootstrap percolation in Ore-type graphs",
"authors": [
"Alexandra Wesolek"
],
"comment": "26 pages, 5 figures",
"categories": [
"math.CO"
],
"abstract": "The $r$-neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as soon as it has $r$ infected neighbours. An inital set of infected vertices is called percolating if at the end of the bootstrap process all vertices are infected. We give Ore-type conditions that guarantee the existence of a small percolating set of size $l\\leq 2r-2$ if the number of vertices $n$ of our graph is sufficiently large: if $l\\geq r$ and satisfies $2r \\geq l+2 \\lfloor \\sqrt{2(l-r)+0.25}+2.5 \\rfloor-1$ then there exists a percolating set of size $l$ for every graph in which any two non-adjacent vertices $x$ and $y$ satisfy $deg(x)+deg(y) \\geq n+4r-2l-2\\lfloor\\sqrt{2(l-r)+0.25}+2.5 \\rfloor-1$ and if $l$ is larger with $l\\leq 2r-2$ there exists a percolating set of size $l$ if $deg(x)+deg(y) \\geq n+2r-l-2$. Our results extend the work of Gunderson, who showed that a graph with minimum degree $\\lfloor n/2 \\rfloor+r-3$ has a percolating set of size $r \\geq 4$. We also give bounds for arbitrarily large $l$ in the minimum degree setting.",
"revisions": [
{
"version": "v1",
"updated": "2019-09-10T17:49:09.000Z"
}
],
"analyses": {
"subjects": [
"05C35",
"05C99",
"G.2.2"
],
"keywords": [
"bootstrap percolation",
"ore-type graphs",
"percolating set",
"minimum degree",
"neighbour bootstrap process"
],
"note": {
"typesetting": "TeX",
"pages": 26,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}