<p>Consider the process where the <i>n</i> vertices of a square 2-dimensional torus appear consecutively in a random order. We show that typically the size of the 3-core of the corresponding induced unit-distance graph transitions from 0 to <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n-o(n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> within a single step. Equivalently, by infecting the vertices of the torus in a random order, under two-neighbour bootstrap percolation, the size of the infected set transitions instantaneously from <i>o</i>(<i>n</i>) to <i>n</i>. This hitting time result answers a question of Benjamini. We also study the much more challenging and general setting of bootstrap percolation on two-dimensional lattices for a variety of finite-range infection rules. In this case, powerful but fragile bootstrap percolation tools such as the rectangles process and the Aizenman–Lebowitz lemma become unavailable. We develop a new method complementing and replacing these standard techniques, thus allowing us to prove the above hitting time result for a wide family of threshold bootstrap percolation rules on the 2-dimensional square lattice, including neighbourhoods given by large <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\ell ^p\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ℓ</mi> <mi>p</mi> </msup> </math></EquationSource> </InlineEquation> balls for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(p\in [1,\infty ]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>1</mn> <mo>,</mo> <mi>∞</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Explosive appearance of cores and bootstrap percolation on lattices

  • Ivailo Hartarsky,
  • Lyuben Lichev

摘要

Consider the process where the n vertices of a square 2-dimensional torus appear consecutively in a random order. We show that typically the size of the 3-core of the corresponding induced unit-distance graph transitions from 0 to \(n-o(n)\) n - o ( n ) within a single step. Equivalently, by infecting the vertices of the torus in a random order, under two-neighbour bootstrap percolation, the size of the infected set transitions instantaneously from o(n) to n. This hitting time result answers a question of Benjamini. We also study the much more challenging and general setting of bootstrap percolation on two-dimensional lattices for a variety of finite-range infection rules. In this case, powerful but fragile bootstrap percolation tools such as the rectangles process and the Aizenman–Lebowitz lemma become unavailable. We develop a new method complementing and replacing these standard techniques, thus allowing us to prove the above hitting time result for a wide family of threshold bootstrap percolation rules on the 2-dimensional square lattice, including neighbourhoods given by large \(\ell ^p\) p balls for \(p\in [1,\infty ]\) p [ 1 , ] .