{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:05:15Z","timestamp":1761609915426},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T00:00:00Z","timestamp":1459382400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Let<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>denote the hypercube of dimension<jats:italic>d<\/jats:italic>. Given<jats:italic>d<\/jats:italic>\u2a7e<jats:italic>m<\/jats:italic>, a spanning subgraph<jats:italic>G<\/jats:italic>of<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>is said to be (<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>,<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>)-saturated if it does not contain<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>as a subgraph but adding any edge of<jats:italic>E<\/jats:italic>(<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>)\\<jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>) creates a copy of<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>in<jats:italic>G<\/jats:italic>. Answering a question of Johnson and Pinto [27], we show that for every fixed<jats:italic>m<\/jats:italic>\u2a7e 2 the minimum number of edges in a (<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>,<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>)-saturated graph is \u0398(2<jats:italic><jats:sup>d<\/jats:sup><\/jats:italic>).<\/jats:p><jats:p>We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>is said to be<jats:italic>weakly<\/jats:italic>(<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>,<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>)-saturated if the edges of<jats:italic>E<\/jats:italic>(<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>)\\<jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>) can be added to<jats:italic>G<\/jats:italic>one at a time so that each added edge creates a new copy of<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>. Answering another question of Johnson and Pinto [27], we determine the minimum number of edges in a weakly (<jats:italic>Q<jats:sub>d<\/jats:sub><\/jats:italic>,<jats:italic>Q<jats:sub>m<\/jats:sub><\/jats:italic>)-saturated graph for all<jats:italic>d<\/jats:italic>\u2a7e<jats:italic>m<\/jats:italic>\u2a7e 1. More generally, we determine the minimum number of edges in a subgraph of the<jats:italic>d<\/jats:italic>-dimensional grid<jats:italic>P<jats:sub>k<\/jats:sub><jats:sup>d<\/jats:sup><\/jats:italic>which is weakly saturated with respect to \u2018axis aligned\u2019 copies of a smaller grid<jats:italic>P<jats:sub>r<\/jats:sub><jats:sup>m<\/jats:sup><\/jats:italic>. We also study weak saturation of cycles in the grid.<\/jats:p>","DOI":"10.1017\/s0963548316000122","type":"journal-article","created":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T06:18:01Z","timestamp":1459405081000},"page":"78-98","source":"Crossref","is-referenced-by-count":6,"title":["Saturation in the Hypercube and Bootstrap Percolation"],"prefix":"10.1017","volume":"26","author":[{"given":"NATASHA","family":"MORRISON","sequence":"first","affiliation":[]},{"given":"JONATHAN A.","family":"NOEL","sequence":"additional","affiliation":[]},{"given":"ALEX","family":"SCOTT","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,3,31]]},"reference":[{"key":"S0963548316000122_ref20","doi-asserted-by":"publisher","DOI":"10.2307\/2311408"},{"key":"S0963548316000122_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.03.005"},{"key":"S0963548316000122_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20508"},{"key":"S0963548316000122_ref14","first-page":"57","article-title":"Minimum critical squarefree subgraph of a hypercube","volume":"189","author":"Choi","year":"2008","journal-title":"Proc. 39th Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer."},{"key":"S0963548316000122_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20458"},{"key":"S0963548316000122_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00173-T"},{"key":"S0963548316000122_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582930"},{"key":"S0963548316000122_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.003"},{"key":"S0963548316000122_ref18","doi-asserted-by":"crossref","unstructured":"Day A. N. (2014) Saturated graphs of prescribed minimum degree. arXiv:1407.6664v1","DOI":"10.1155\/2014\/316108"},{"key":"S0963548316000122_ref25","doi-asserted-by":"crossref","DOI":"10.37236\/1055","article-title":"Constructive upper bounds for cycle-saturated graphs of minimum size","volume":"13","author":"Gould","year":"2006","journal-title":"Electron. J. Combin."},{"key":"S0963548316000122_ref37","first-page":"163","article-title":"On some properties of linear complexes","volume":"24","author":"Zykov","year":"1949","journal-title":"Mat. Sbornik"},{"key":"S0963548316000122_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.02.009"},{"key":"S0963548316000122_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004746"},{"key":"S0963548316000122_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190160311"},{"key":"S0963548316000122_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(85)90048-2"},{"key":"S0963548316000122_ref2","unstructured":"Baber R. (2012) Tur\u00e1n densities of hypercubes. arXiv:1201.3587v2"},{"key":"S0963548316000122_ref30","volume-title":"The Theory of Error-Correcting Codes I","author":"MacWilliams","year":"1977"},{"key":"S0963548316000122_ref34","unstructured":"Pikhurko O. (1999) Extremal hypergraphs. PhD thesis, University of Cambridge."},{"key":"S0963548316000122_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309009985"},{"key":"S0963548316000122_ref28","first-page":"189","volume-title":"Convexity and Graph Theory: Jerusalem 1981","author":"Kalai","year":"1984"},{"key":"S0963548316000122_ref9","unstructured":"Bollob\u00e1s B. (1968) Weakly k-saturated graphs. In Beitr\u00e4ge zur Graphentheorie: Kolloquium, Manebach 1967, Teubner, pp. 25\u201331."},{"key":"S0963548316000122_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90692-9"},{"key":"S0963548316000122_ref21","article-title":"A survey of minimum saturated graphs","volume":"18","author":"Faudree","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548316000122_ref32","doi-asserted-by":"crossref","DOI":"10.37236\/4136","article-title":"On saturated k-Sperner systems","volume":"21","author":"Morrison","year":"2014","journal-title":"Electron. J. Combin."},{"key":"S0963548316000122_ref33","unstructured":"Ollmann L. T. (1972) K 2,2 saturated graphs with a minimal number of edges. In Proc. 3rd South-eastern Conference on Combinatorics, Graph Theory, and Computing: Boca Raton 1972, pp. 367\u2013392."},{"key":"S0963548316000122_ref31","volume-title":"The Theory of Error-Correcting Codes II","author":"MacWilliams","year":"1977"},{"key":"S0963548316000122_ref17","doi-asserted-by":"crossref","DOI":"10.37236\/383","article-title":"An extremal theorem in the hypercube","volume":"17","author":"Conlon","year":"2010","journal-title":"Electron. J. Combin."},{"key":"S0963548316000122_ref3","doi-asserted-by":"crossref","unstructured":"Balister P. N. , Bollob\u00e1s B. , Lee J. D. and Narayanan B. P. Line percolation, Random Struct. Alg., to appear.","DOI":"10.1002\/rsa.20755"},{"key":"S0963548316000122_ref27","unstructured":"Johnson J. R. and Pinto T. (2014) Saturated subgraphs of the hypercube. arXiv:1406.1766v1"},{"key":"S0963548316000122_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0451-6"},{"key":"S0963548316000122_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20372"},{"key":"S0963548316000122_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170405"},{"key":"S0963548316000122_ref19","unstructured":"Erd\u0151s P. (1984) On some problems in graph theory, combinatorial analysis and combinatorial number theory. In Graph Theory and Combinatorics: Cambridge 1983, Academic, pp. 1\u201317."},{"key":"S0963548316000122_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190190104"},{"key":"S0963548316000122_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"S0963548316000122_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21668"},{"key":"S0963548316000122_ref10","unstructured":"Bollob\u00e1s B. (1978) Extremal graph theory, Vol. 11 of London Mathematical Society Monographs, Academic."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T00:32:04Z","timestamp":1600389124000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000122\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,31]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["S0963548316000122"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000122","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,31]]}}}