Nota sobre o tempo mínimo de infecção em 2-neighbour bootstrap percolation em grids partindo de n + 1 vértices
Resumo
Estudamos o “2-neighbour bootstrap percolation” em grids n × n partindo de conjuntos inicialmente infectados de tamanho exatamente n + 1. Mostramos que o tempo mínimo de percolação para n ≥ 1, neste caso, é n − 1 caso n ≢ 3 (mod 4) e n − 2 caso n ≡ 3 (mod 4).
Referências
Adler, J. and Lev, U. (2003). Bootstrap percolation: visualizations and applications. Brazilian Journal of Physics, 33:641–644.
Balogh, J., Bollobás, B., Duminil-Copin, H., and Morris, R. (2012). The sharp threshold for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society, 364(5):2667–2701.
Balogh, J., Bollobás, B., and Morris, R. (2010). Bootstrap percolation in high dimensions. Combinatorics, Probability and Computing, 19(5-6):643–692.
Balogh, J. and Pete, G. (1998). Random disease on the square grid. Random Structures & Algorithms, 13(3-4):409–422.
Benevides, F., Bermond, J.-C., Lesfari, H., and Nisse, N. (2021). Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. PhD thesis, Université Côte d’Azur.
Benevides, F. and Przykucki, M. (2015). Maximum percolation time in two-dimensional bootstrap percolation. SIAM Journal on Discrete Mathematics, 29(1):224–251.
Bessy, S., Ehard, S., Penso, L. D., and Rautenbach, D. (2019). Dynamic monopolies for interval graphs with bounded thresholds. Discrete Applied Mathematics, 260:256–261.
Bollobás, B., Holmgren, C., Smith, P., and Uzzell, A. J. (2014). The time of bootstrap percolation with dense initial sets. The Annals of Probability, 42(4):1337–1373.
Chalupa, J., Leath, P. L., and Reich, G. R. (1979). Bootstrap percolation on a bethe lattice. Journal of Physics C: Solid State Physics, 12(1):L31.
Chen, N. (2009). On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400–1415.
Guggiola, A. and Semerjian, G. (2015). Minimal contagious sets in random regular graphs. Journal of Statistical Physics, 158:300–358.
Morris, R. (2009). Minimal percolating sets in bootstrap percolation. The Electronic Journal of Combinatorics, 16(R2):1.
Pete, G. (1997). Disease processes and bootstrap percolation. PhD thesis, Bolyai Institute, Jzsef Attila University, Szeged.
Przykucki, M. and Shelton, T. (2020). Smallest percolating sets in bootstrap percolation on grids. The Electronic Journal of Combinatorics, pages P4–34.
Riedl, E. (2012). Largest and smallest minimal percolating sets in trees. The Electronic Journal of Combinatorics, pages P64–P64.
Balogh, J., Bollobás, B., Duminil-Copin, H., and Morris, R. (2012). The sharp threshold for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society, 364(5):2667–2701.
Balogh, J., Bollobás, B., and Morris, R. (2010). Bootstrap percolation in high dimensions. Combinatorics, Probability and Computing, 19(5-6):643–692.
Balogh, J. and Pete, G. (1998). Random disease on the square grid. Random Structures & Algorithms, 13(3-4):409–422.
Benevides, F., Bermond, J.-C., Lesfari, H., and Nisse, N. (2021). Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. PhD thesis, Université Côte d’Azur.
Benevides, F. and Przykucki, M. (2015). Maximum percolation time in two-dimensional bootstrap percolation. SIAM Journal on Discrete Mathematics, 29(1):224–251.
Bessy, S., Ehard, S., Penso, L. D., and Rautenbach, D. (2019). Dynamic monopolies for interval graphs with bounded thresholds. Discrete Applied Mathematics, 260:256–261.
Bollobás, B., Holmgren, C., Smith, P., and Uzzell, A. J. (2014). The time of bootstrap percolation with dense initial sets. The Annals of Probability, 42(4):1337–1373.
Chalupa, J., Leath, P. L., and Reich, G. R. (1979). Bootstrap percolation on a bethe lattice. Journal of Physics C: Solid State Physics, 12(1):L31.
Chen, N. (2009). On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400–1415.
Guggiola, A. and Semerjian, G. (2015). Minimal contagious sets in random regular graphs. Journal of Statistical Physics, 158:300–358.
Morris, R. (2009). Minimal percolating sets in bootstrap percolation. The Electronic Journal of Combinatorics, 16(R2):1.
Pete, G. (1997). Disease processes and bootstrap percolation. PhD thesis, Bolyai Institute, Jzsef Attila University, Szeged.
Przykucki, M. and Shelton, T. (2020). Smallest percolating sets in bootstrap percolation on grids. The Electronic Journal of Combinatorics, pages P4–34.
Riedl, E. (2012). Largest and smallest minimal percolating sets in trees. The Electronic Journal of Combinatorics, pages P64–P64.
Publicado
06/08/2023
Como Citar
BENEVIDES, Fabrício S.; PASCOAL, Matheus A. S..
Nota sobre o tempo mínimo de infecção em 2-neighbour bootstrap percolation em grids partindo de n + 1 vértices. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 69-73.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230893.
