{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T11:52:23Z","timestamp":1768218743198,"version":"3.49.0"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:00:00Z","timestamp":1760572800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We prove that determining the weak saturation number of a host graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100187_inline1.png\"\/>\n                        <jats:tex-math>$F$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with respect to a pattern graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100187_inline2.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is computationally hard, even when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100187_inline3.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the triangle. Our main tool establishes a connection between weak saturation and the shellability of simplicial complexes.\n                  <\/jats:p>","DOI":"10.1017\/s0963548325100187","type":"journal-article","created":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T11:59:59Z","timestamp":1760615999000},"page":"83-88","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["A note on the computational complexity of weak saturation"],"prefix":"10.1017","volume":"35","author":[{"given":"Martin","family":"Tancer","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/024d6js02","id-type":"ROR","asserted-by":"publisher"}],"name":"Charles University"}]},{"given":"Mykhaylo","family":"Tyomkyn","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/024d6js02","id-type":"ROR","asserted-by":"publisher"}],"name":"Charles University"}]}],"member":"56","published-online":{"date-parts":[[2025,10,16]]},"reference":[{"key":"S0963548325100187_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.03.005"},{"key":"S0963548325100187_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3314024"},{"key":"S0963548325100187_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s003730170012"},{"key":"S0963548325100187_ref23","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/16197"},{"key":"S0963548325100187_ref25","unstructured":"[25] Tuza, Z. (1988) Extremal problems on saturated graphs and hypergraphs. In Eleventh British Combinatorial Conference (London, 1987), vol. 25, pp. 105\u2013113."},{"key":"S0963548325100187_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90035-Z"},{"key":"S0963548325100187_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004746"},{"key":"S0963548325100187_ref22","volume-title":"Introduction to Piecewise-Linear Topology","author":"Rourke","year":"1982"},{"key":"S0963548325100187_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2014.07.012"},{"key":"S0963548325100187_ref19","volume-title":"Elements of Algebraic Topology","author":"Munkres","year":"1984"},{"key":"S0963548325100187_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/22M1523960"},{"key":"S0963548325100187_ref16","unstructured":"[16] Lov\u00e1sz, L. (1977) Flats in matroids and geometric graphs. In Combinatorial Surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), pp. 45\u201386."},{"key":"S0963548325100187_ref27","unstructured":"[27] Terekhov, N. and Zhukovskii, M. (2023) Weak saturation in graphs: a combinatorial approach, arXiv preprint arXiv:2305.11043."},{"key":"S0963548325100187_ref28","doi-asserted-by":"crossref","unstructured":"[28] Terekhov, N. and Zhukovskii, M. (2024) Weak saturation rank: a failure of linear algebraic approach to weak saturation, arXiv preprint arXiv:2405.17857.","DOI":"10.1007\/s00493-025-00174-y"},{"key":"S0963548325100187_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90692-9"},{"key":"S0963548325100187_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2017.11.018"},{"key":"S0963548325100187_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<409::AID-RSA11>3.0.CO;2-U"},{"key":"S0963548325100187_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80025-5"},{"key":"S0963548325100187_ref7","unstructured":"[7] Chakraborti, D. , Cho, M. , Kim, J. and Kim, M. (2024) Colorful fractional Helly theorem via weak saturation, arXiv preprint arXiv:2408.15093."},{"key":"S0963548325100187_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582930"},{"key":"S0963548325100187_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.08.004"},{"key":"S0963548325100187_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.10.023"},{"key":"S0963548325100187_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-023-00049-0"},{"key":"S0963548325100187_ref13","volume-title":"Algebraic Topology","author":"Hatcher","year":"2002"},{"key":"S0963548325100187_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128673"},{"key":"S0963548325100187_ref14","first-page":"189","volume-title":"Convexity and Graph Theory (Jerusalem 1981)","author":"Kalai","year":"1984"},{"key":"S0963548325100187_ref4","first-page":"25","volume-title":"Beitr\u00e4ge zur Graphentheorie (Kolloquium, Manebach, 1967)","author":"Bollob\u00e1s","year":"1968"},{"key":"S0963548325100187_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(85)90048-2"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325100187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T08:49:22Z","timestamp":1768207762000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325100187\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,16]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["S0963548325100187"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325100187","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives licence (https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided that no alterations are made and the original article is properly cited. The written permission of Cambridge University Press must be obtained prior to any commercial use and\/or adaptation of the article.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}