{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:18Z","timestamp":1787323518559,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00c3\u00a1nyos Akad\u00c3\u00a9mia","doi-asserted-by":"publisher","award":["LP2017-19\/2017"],"award-info":[{"award-number":["LP2017-19\/2017"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00c3\u00a1si Fejleszt\u00c3\u00a9si \u00c3\u00a9s Innov\u00c3\u00a1ci\u00c3\u00b3s Hivatal","doi-asserted-by":"publisher","award":["K 132696"],"award-info":[{"award-number":["K 132696"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>A 0-1 matrix $M$ is saturating for a 0-1 matrix $P$ if $M$ does not contain a submatrix that can be turned into $P$ by changing some 1 entries to 0 entries, and changing an arbitrary 0 to 1 in $M$ introduces such a submatrix in $M$. In saturation problems for 0-1 matrices we are interested in estimating the minimum number of 1 entries in an $m \\times n$ matrix that is saturating for $P$, in terms of $m$ and $n$. In other words, we wish to give good estimates for the saturation function of $P$. Recently, Brualdi and Cao [R. A. Brualdi and L. Cao, preprint, arXiv:2005.00379, 2020] initiated the study of saturation problems in the context of 0-1 matrices. We extend their work in several directions. We prove that every 0-1 forbidden matrix has its saturation function either in $\\Theta(1)$ or $\\Theta(n)$ in the case when we restrict ourselves to square saturating matrices. Then we give a partial answer to a question posed by Brualdi and Cao about the saturation function of $J_k$, which is obtained from the identity matrix $I_k$ by putting the first row after the last row. Furthermore, we exhibit a $5\\times 5$ permutation matrix with the saturation function bounded from the above by a fixed constant. We complement this result by identifying large classes of 0-1 matrices with linear saturation function. Finally, we completely resolve the related semisaturation problem as far as the constant versus linear dichotomy is concerned.<\/jats:p>","DOI":"10.1137\/20m1376327","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T18:06:33Z","timestamp":1630433193000},"page":"1964-1977","source":"Crossref","is-referenced-by-count":3,"title":["Saturation Problems about Forbidden 0-1 Submatrices"],"prefix":"10.1137","volume":"35","author":[{"given":"Radoslav","family":"Fulek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3839-5103","authenticated-orcid":true,"given":"Bal\u00e1zs","family":"Keszegh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"key":"atypb1","unstructured":"R. A. Brualdi and L. Cao,\n                      Pattern-avoiding (0, 1)-matrices\n                      , preprint, arXiv:2005.00379, 2020, http:\/\/arxiv.org\/abs\/2005.00379."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103321"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1199-2"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.2307\/2311408"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.06.010"},{"key":"atypb6","unstructured":"N. Frankl, S. Kiselev, A. Kupavskii, and B. Patk\u00f3s,\n                      VC-saturated set systems\n                      , preprint, arXiv:2005.12545, 2020, http:\/\/arxiv.org\/abs\/2005.12545."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21668"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.02.040"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90074-7"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.03.004"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1195-6"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.05.006"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2021.105497"},{"key":"atypb15","first-page":"250","author":"Klazar M.","year":"2000","journal-title":"Heidelberg"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2019.01.006"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100209"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758836"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773960"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.06.020"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.11.015"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1376327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:10Z","timestamp":1787321230000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1376327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1376327"],"URL":"https:\/\/doi.org\/10.1137\/20m1376327","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}