{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T15:07:20Z","timestamp":1779376040599,"version":"3.53.1"},"reference-count":16,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>\n                    Given a fixed graph\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>H<\/mml:mi>\n                    <\/mml:math>\n                    and an\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:math>\n                    -vertex graph\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    , the\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>H<\/mml:mi>\n                    <\/mml:math>\n                    <jats:italic>-bootstrap percolation process<\/jats:italic>\n                    on\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    is defined to be the sequence of graphs\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mi>i<\/mml:mi>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    ,\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>i<\/mml:mi>\n                        <mml:mo>\u2265<\/mml:mo>\n                        <mml:mn>0<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    which starts with\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msub>\n                          <mml:mi>G<\/mml:mi>\n                          <mml:mn>0<\/mml:mn>\n                        <\/mml:msub>\n                        <mml:mo>:<\/mml:mo>\n                        <mml:mo>=<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    and in which\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mi>i<\/mml:mi>\n                          <mml:mo>+<\/mml:mo>\n                          <mml:mn>1<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    is obtained from\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mi>i<\/mml:mi>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    by adding every edge that completes a copy of\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>H<\/mml:mi>\n                    <\/mml:math>\n                    . We are interested in\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msub>\n                          <mml:mi>M<\/mml:mi>\n                          <mml:mi>H<\/mml:mi>\n                        <\/mml:msub>\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    which is the maximum number of steps, over all\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:math>\n                    -vertex graphs\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    , that this process takes to stabilise. We determine this maximum running time precisely when\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>H<\/mml:mi>\n                    <\/mml:math>\n                    is a cycle, giving the first infinite family of graphs\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>H<\/mml:mi>\n                    <\/mml:math>\n                    for which an exact solution is known. We find that\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msub>\n                          <mml:mi>M<\/mml:mi>\n                          <mml:msub>\n                            <mml:mi>C<\/mml:mi>\n                            <mml:mi>k<\/mml:mi>\n                          <\/mml:msub>\n                        <\/mml:msub>\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    is of order\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msub>\n                          <mml:mo form=\"prefix\">log<\/mml:mo>\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:msub>\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    for all\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mn>3<\/mml:mn>\n                        <mml:mo>\u2264<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>\u2208<\/mml:mo>\n                        <mml:mi>\u2115<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    . Interestingly though, the function exhibits different behaviour depending on the parity of\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:math>\n                    and the exact location of the values of\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:math>\n                    for which\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msub>\n                          <mml:mi>M<\/mml:mi>\n                          <mml:mi>H<\/mml:mi>\n                        <\/mml:msub>\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    increases is determined by the Frobenius number of a certain numerical semigroup depending on\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:math>\n                    .\n                  <\/jats:p>","DOI":"10.5802\/igt.19","type":"journal-article","created":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T09:28:38Z","timestamp":1775122118000},"page":"89-126","source":"Crossref","is-referenced-by-count":0,"title":["Slow graph bootstrap percolation I: Cycles"],"prefix":"10.5802","volume":"3","author":[{"given":"David","family":"Fabian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick","family":"Morris","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya (UPC), Departament de Matem\u00e0tiques, Carrer de Jordi Girona, 31, Barcelona, 08034 (Spain)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tibor","family":"Szab\u00f3","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Institute of Mathematics, Kaiserswerther Str. 16-18, Berlin, 14195 (Germany)"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"3842","published-online":{"date-parts":[[2026,4,2]]},"reference":[{"key":"key2026052116243576697_1","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1590\/S0103-97332003000300031","article-title":"Bootstrap percolation: visualizations and applications","volume":"33","author":"Adler, Joan","year":"2003","unstructured":"[1] Adler, Joan; Lev, Uri Bootstrap percolation: visualizations and applications, Braz. J. Phys., Volume 33 (2003), pp. 641-644","journal-title":"Braz. J. Phys."},{"key":"key2026052116243576697_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198568209.001.0001","author":"Alfons\u00edn, Jorge L Ram\u00edrez","year":"2005","unstructured":"[2] Alfons\u00edn, Jorge L Ram\u00edrez The Diophantine Frobenius Problem, Oxford University Press, 2005","journal-title":"The Diophantine Frobenius Problem"},{"issue":"4","key":"key2026052116243576697_3","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/rsa.20458","article-title":"Graph bootstrap percolation","volume":"41","author":"Balogh, J\u00f3zsef","year":"2012","unstructured":"[3] Balogh, J\u00f3zsef; Bollob\u00e1s, B\u00e9la; Morris, Robert Graph bootstrap percolation, Random Struct. Algorithms, Volume 41 (2012) no. 4, pp. 413-440","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"key2026052116243576697_4","doi-asserted-by":"publisher","first-page":"1359","DOI":"10.1090\/proc\/15130","article-title":"The maximum length of <span class=\"mathjax-formula\" data-tex=\"${K}_r $\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><msub><mi>K<\/mi> <mi>r<\/mi> <\/msub><\/math><\/span>-bootstrap percolation","volume":"154","author":"Balogh, J\u00f3zsef","year":"2026","unstructured":"[4] Balogh, J\u00f3zsef; Kronenberg, Gal; Pokrovskiy, Alexey; Szab\u00f3, Tibor The maximum length of K r -bootstrap percolation, Proc. Am. Math. Soc., Volume 154 (2026) no. 4, pp. 1359-1371","journal-title":"Proc. Am. Math. Soc."},{"issue":"12","key":"key2026052116243576697_5","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1073\/pnas.32.12.331","article-title":"On sets of integers which contain no three terms in arithmetical progression","volume":"32","author":"Behrend, Felix A.","year":"1946","unstructured":"[5] Behrend, Felix A. On sets of integers which contain no three terms in arithmetical progression, Proc. Natl. Acad. Sci. USA, Volume 32 (1946) no. 12, pp. 331-332","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"key2026052116243576697_6","first-page":"25","article-title":"Weakly k-saturated graphs","author":"Bollob\u00e1s, B\u00e9la","year":"1968","unstructured":"[6] Bollob\u00e1s, B\u00e9la Weakly k-saturated graphs, Beitr\u00e4ge zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner Verlagsgesellschaft (1968), pp. 25-31","journal-title":"Beitr\u00e4ge zur Graphentheorie (Kolloquium, Manebach, 1967)"},{"issue":"2","key":"key2026052116243576697_7","doi-asserted-by":"publisher","DOI":"10.37236\/5771","article-title":"On the maximum running time in graph bootstrap percolation","volume":"24","author":"Bollob\u00e1s, B\u00e9la","year":"2017","unstructured":"[7] Bollob\u00e1s, B\u00e9la; Przykucki, Micha\u0142; Riordan, Oliver; Sahasrabudhe, Julian On the maximum running time in graph bootstrap percolation, Electron. J. Comb., Volume 24 (2017) no. 2, P2.16, 20 pages","journal-title":"Electron. J. Comb."},{"issue":"1","key":"key2026052116243576697_8","article-title":"Bootstrap percolation on a Bethe lattice","volume":"12","author":"Chalupa, John","year":"1979","unstructured":"[8] Chalupa, John; Leath, Paul L.; Reich, Gary R. Bootstrap percolation on a Bethe lattice, J. Phys. C. Solid State Phys., Volume 12 (1979) no. 1, L31","journal-title":"J. Phys. C. Solid State Phys."},{"key":"key2026052116243576697_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103783","article-title":"Long running times for hypergraph bootstrap percolation","volume":"115","author":"Espuny D\u00edaz, Alberto","year":"2024","unstructured":"[9] Espuny D\u00edaz, Alberto; Janzer, Barnab\u00e1s; Kronenberg, Gal; Lada, Joanna Long running times for hypergraph bootstrap percolation, Eur. J. Comb., Volume 115 (2024), 103783, 18 pages","journal-title":"Eur. J. Comb."},{"key":"key2026052116243576697_10","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.jctb.2024.12.006","article-title":"Slow graph bootstrap percolation II: Accelerating properties","volume":"172","author":"Fabian, David","year":"2025","unstructured":"[10] Fabian, David; Morris, Patrick; Szab\u00f3, Tibor Slow graph bootstrap percolation II: Accelerating properties, J. Comb. Theory, Ser. B, Volume 172 (2025), pp. 44-79","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"key2026052116243576697_11","doi-asserted-by":"publisher","first-page":"1462","DOI":"10.1137\/22M151995X","article-title":"The maximal running time of hypergraph bootstrap percolation","volume":"38","author":"Hartarsky, Ivailo","year":"2024","unstructured":"[11] Hartarsky, Ivailo; Lichev, Lyuben The maximal running time of hypergraph bootstrap percolation, SIAM J. Discrete Math., Volume 38 (2024) no. 2, pp. 1462-1471","journal-title":"SIAM J. Discrete Math."},{"key":"key2026052116243576697_12","author":"Matzke, Kilian","year":"2015","unstructured":"[12] Matzke, Kilian The saturation time of graph bootstrap percolation (2015)","journal-title":"The saturation time of graph bootstrap percolation"},{"key":"key2026052116243576697_13","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.ejc.2017.06.024","article-title":"Bootstrap percolation, and other automata","volume":"66","author":"Morris, Robert","year":"2017","unstructured":"[13] Morris, Robert Bootstrap percolation, and other automata, Eur. J. Comb., Volume 66 (2017), pp. 250-263","journal-title":"Eur. J. Comb."},{"issue":"2","key":"key2026052116243576697_14","doi-asserted-by":"publisher","DOI":"10.37236\/11307","article-title":"On the running time of hypergraph bootstrap percolation","volume":"30","author":"Noel, Jonathan A.","year":"2023","unstructured":"[14] Noel, Jonathan A.; Ranganathan, Arjun On the running time of hypergraph bootstrap percolation, Electron. J. Comb., Volume 30 (2023) no. 2, P2.46, 20 pages","journal-title":"Electron. J. Comb."},{"issue":"2","key":"key2026052116243576697_15","doi-asserted-by":"publisher","DOI":"10.37236\/2412","article-title":"Maximal percolation time in hypercubes under 2-bootstrap percolation","volume":"19","author":"Przykucki, Micha\u0142","year":"2012","unstructured":"[15] Przykucki, Micha\u0142 Maximal percolation time in hypercubes under 2-bootstrap percolation, Electron. J. Comb., Volume 19 (2012) no. 2, P41, 13 pages","journal-title":"Electron. J. Comb."},{"key":"key2026052116243576697_16","author":"Neumann, John","year":"1966","unstructured":"[16] Neumann, John Theory of self-reproducing automata, University of Illinois Press, Urbana, 1966, xix+388 pages","journal-title":"Theory of self-reproducing automata"}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T14:24:43Z","timestamp":1779373483000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.19\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":16,"alternative-id":["10.5802\/igt.19"],"URL":"https:\/\/doi.org\/10.5802\/igt.19","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}