{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:06:28Z","timestamp":1761599188413,"version":"build-2065373602"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T00:00:00Z","timestamp":1758240000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T00:00:00Z","timestamp":1758240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"Abstract<\/jats:title>\n \n Given a graph\n F<\/jats:italic>\n and a positive integer\n n<\/jats:italic>\n , the weak\n F<\/jats:italic>\n -saturation number\n \n \n $${\\textrm{wsat}}(K_n,F)$$<\/jats:tex-math>\n \n \n wsat<\/mml:mtext>\n (<\/mml:mo>\n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n ,<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the minimum number of edges in a graph\n H<\/jats:italic>\n on\n n<\/jats:italic>\n vertices such that the edges missing in\n H<\/jats:italic>\n can be added, one at a time, so that every edge creates a copy of\n F<\/jats:italic>\n . Kalai in 1985 introduced a linear algebraic approach that became one of the most efficient tools to prove lower bounds on weak saturation numbers. Let\n W<\/jats:italic>\n be a vector space spanned by vectors\n w<\/jats:italic>\n (\n e<\/jats:italic>\n ) assigned to edges\n e<\/jats:italic>\n of\n \n \n $$K_n$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Suppose that, for every copy\n \n \n $$F'\\subset K_n$$<\/jats:tex-math>\n \n \n \n F<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2282<\/mml:mo>\n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of\n F<\/jats:italic>\n , there exist non-zero scalars\n \n \n $$\\lambda _e$$<\/jats:tex-math>\n \n \n \u03bb<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$e\\in E(F')$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n \n F<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , satisfying\n \n \n $$\\sum _{e\\in E(F')}\\lambda _e w(e)=0$$<\/jats:tex-math>\n \n \n \n \u2211<\/mml:mo>\n \n e<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n \n F<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n \n \u03bb<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msub>\n w<\/mml:mi>\n \n (<\/mml:mo>\n e<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Then\n \n \n $$\\textrm{dim}W\\le {\\textrm{wsat}}(K_n,F)$$<\/jats:tex-math>\n \n \n dim<\/mml:mtext>\n W<\/mml:mi>\n \u2264<\/mml:mo>\n wsat<\/mml:mtext>\n (<\/mml:mo>\n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n ,<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In this paper, we prove limitations of this approach: we find infinitely many\n F<\/jats:italic>\n such that, for every vector space\n W<\/jats:italic>\n as above,\n \n \n $$\\textrm{dim}W<{\\textrm{wsat}}(K_n,F)$$<\/jats:tex-math>\n \n \n dim<\/mml:mtext>\n W<\/mml:mi>\n <<\/mml:mo>\n wsat<\/mml:mtext>\n (<\/mml:mo>\n \n K<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n ,<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We also introduce a modification of this approach that yields tight lower bounds even when the original direct approach is insufficient. Finally, we generalise our results to random graphs, complete multipartite graphs, and hypergraphs.\n <\/jats:p>","DOI":"10.1007\/s00493-025-00174-y","type":"journal-article","created":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:29:12Z","timestamp":1758274152000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Weak saturation rank: a failure of the linear algebraic approach to weak saturation"],"prefix":"10.1007","volume":"45","author":[{"given":"Nikolai","family":"Terekhov","sequence":"first","affiliation":[]},{"given":"Maksim","family":"Zhukovskii","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,19]]},"reference":[{"key":"174_CR1","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1590\/S0103-97332003000300031","volume":"33","author":"J Adler","year":"2003","unstructured":"Adler, J., Lev, U.: Bootstrap percolation: visualizations and applications. Braz. J. Phys. 33, 641\u2013644 (2003)","journal-title":"Braz. J. Phys."},{"key":"174_CR2","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0097-3165(85)90048-2","volume":"40","author":"N Alon","year":"1985","unstructured":"Alon, N.: An extremal problem for sets with applications to graph theory. Journal of Combinatorial Theory, Series A 40, 82\u201389 (1985)","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"6","key":"174_CR3","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1016\/j.jcta.2012.03.005","volume":"119","author":"J Balogh","year":"2012","unstructured":"Balogh, J., Bollob\u00e1s, B., Morris, R., Riordan, O.: Linear algebra and bootstrap percolation. Journal of Combinatorial Theory, Series A 119(6), 1328\u20131335 (2012)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"174_CR4","unstructured":"Bollob\u00e1s, B.: Weakly $$k$$-saturated graphs, Beitr\u00e4ge zur Graphentheorie (Kolloquium, Manebach, 1967): Teubner. Leipzig 1968, 25\u201331"},{"key":"174_CR5","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.1007\/s00493-023-00049-0","volume":"43","author":"D Bulavka","year":"2023","unstructured":"Bulavka, D., Tancer, M., Tyomkyn, M.: Weak saturation of multipartite hypergraphs. Combinatorica 43, 1081\u20131102 (2023)","journal-title":"Combinatorica"},{"key":"174_CR6","unstructured":"Edmonds, J., Rota, G.-C.: Submodular set functions, Waterloo Combinatorics Conference, (1966)"},{"key":"174_CR7","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s002200200658","volume":"228","author":"LR Fontes","year":"2002","unstructured":"Fontes, L.R., Schonmann, R.H., Sidoravicius, V.: Stretched exponential fixation in stochastic ising models at zero temperature. Comm. Math. Phys. 228, 495\u2013518 (2002)","journal-title":"Comm. Math. Phys."},{"key":"174_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0195-6698(82)80025-5","volume":"3","author":"P Frankl","year":"1982","unstructured":"Frankl, P.: An extremal problem for two families of sets. European J. Combin. 3, 125\u2013127 (1982)","journal-title":"European J. Combin."},{"key":"174_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.jctb.2023.10.012","volume":"165","author":"B Jackson","year":"2024","unstructured":"Jackson, B., Tanigawa, S.: Maximal matroids in weak order posets. Journal of Combinatorial Theory, Series B 165, 20\u201346 (2024)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"174_CR10","doi-asserted-by":"crossref","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random graphs. J. Wiley & Sons (2000)","DOI":"10.1002\/9781118032718"},{"key":"174_CR11","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF02582930","volume":"1","author":"G Kalai","year":"1985","unstructured":"Kalai, G.: Hyperconnectivity of graphs. Graphs Combin. 1, 65\u201379 (1985)","journal-title":"Graphs Combin."},{"key":"174_CR12","doi-asserted-by":"crossref","unstructured":"Kalai, G.: Weakly saturated graphs are rigid, in: Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., 87, Ann. Discrete Math., 20, North-Holland, Amsterdam, pp. 189\u2013190 (1984)","DOI":"10.1016\/S0304-0208(08)72824-X"},{"key":"174_CR13","unstructured":"Kalinichenko, O., Miralaei, M., Mohammadian, A., Tayfeh-Rezaie, B.: Weak saturation numbers in random graphs, (2023) https:\/\/arxiv.org\/pdf\/2306.10375.pdf"},{"key":"174_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103777","volume":"114","author":"O Kalinichenko","year":"2023","unstructured":"Kalinichenko, O., Zhukovskii, M.: Weak saturation stability. Eur. J. Comb. 114, 103777 (2023)","journal-title":"Eur. J. Comb."},{"key":"174_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2020.105357","volume":"178","author":"G Kronenberg","year":"2021","unstructured":"Kronenberg, G., Martins, T., Morrison, N.: Weak saturation numbers of complete bipartite graphs in the clique. Journal of Combinatorial Theory, Series A 178, 105357 (2021)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"174_CR16","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1016\/j.disc.2007.07.104","volume":"308","author":"A Lee","year":"2008","unstructured":"Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discret. Math. 308, 1425\u20131437 (2008)","journal-title":"Discret. Math."},{"key":"174_CR17","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s00440-009-0259-x","volume":"149","author":"R Morris","year":"2011","unstructured":"Morris, R.: Zero-temperature glauber dynamics on $${\\mathbb{z} }^d$$. Probab. Theory Related Fields 149, 417\u2013434 (2011)","journal-title":"Probab. Theory Related Fields"},{"key":"174_CR18","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1017\/S0963548316000122","volume":"26","author":"N Morrison","year":"2017","unstructured":"Morrison, N., Noel, J.A., Scott, A.: Saturation in the hypercube and bootstrap percolation. Combinatorics, Probability & Computing 26, 78\u201398 (2017)","journal-title":"Combinatorics, Probability & Computing"},{"key":"174_CR19","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.jctb.2014.08.004","volume":"111","author":"G Moshkovitz","year":"2015","unstructured":"Moshkovitz, G., Shapira, A.: Exact bounds for some hypergraph saturation problems. Journal of Combinatorial Theory B 111, 242\u2013248 (2015)","journal-title":"Journal of Combinatorial Theory B"},{"key":"174_CR20","volume-title":"Theory of Self-Reproducing Automata","author":"J von Neumann","year":"1966","unstructured":"von Neumann, J.: Theory of Self-Reproducing Automata. Univ. Illinois Press, Urbana (1966)"},{"key":"174_CR21","volume-title":"Matroid theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid theory. Oxford Univ, Press (1992)"},{"key":"174_CR22","unstructured":"Pikhurko, O.: Extremal hypergraphs, PhD thesis, University of Cambridge, (1999)"},{"key":"174_CR23","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1017\/S0963548301004746","volume":"10","author":"O Pikhurko","year":"2001","unstructured":"Pikhurko, O.: Weakly saturated hypergraphs and exterior algebras. Comb. Probab. Comput. 10, 435\u2013351 (2001)","journal-title":"Comb. Probab. Comput."},{"issue":"7","key":"174_CR24","doi-asserted-by":"publisher","first-page":"2795","DOI":"10.1090\/proc\/16197","volume":"151","author":"A Shapira","year":"2023","unstructured":"Shapira, A., Tyomkyn, M.: Weakly saturated hypergraphs and a conjecture of tuza. Proceedings of the American Mathematical Society 151(7), 2795\u20132805 (2023)","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"2","key":"174_CR25","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0097-3165(90)90070-D","volume":"55","author":"J Spencer","year":"1990","unstructured":"Spencer, J.: Counting extensions. Journal of Combinatorial Theory, Series A 55(2), 247\u2013255 (1990)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"174_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.jctb.2024.12.007","volume":"172","author":"N Terekhov","year":"2025","unstructured":"Terekhov, N., Zhukovskii, M.: Weak saturation in graphs: a combinatorial approach. Journal of Combinatorial Theory, Series B 172, 146\u2013167 (2025)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"174_CR27","doi-asserted-by":"crossref","unstructured":"Tuza, Z.: Asymptotic growth of sparse saturated structures is locally determined. Discrete Math. 108(1\u20133), 397\u2013402 (1992). (Topological, algebraical and combinatorial structures. Frol\u00edk 's memorial volume)","DOI":"10.1016\/0012-365X(92)90692-9"},{"key":"174_CR28","unstructured":"Ulam, S.: Random processes and transformations, Proc. Internat. Congr. Math. 264\u2013275 (1950)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00174-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00174-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00174-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:02:23Z","timestamp":1761598943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00174-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,19]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["174"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00174-y","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,9,19]]},"assertion":[{"value":"4 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"45"}}