{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:17:21Z","timestamp":1759335441163},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T00:00:00Z","timestamp":1550620800000},"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":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic>partial Latin square<jats:italic>P<\/jats:italic>is called<jats:italic>\u03b1<\/jats:italic>-dense if each row and column has at most<jats:italic>\u03b1n<\/jats:italic>non-empty cells and each symbol occurs at most<jats:italic>\u03b1n<\/jats:italic>times in<jats:italic>P<\/jats:italic>. An<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic>array<jats:italic>A<\/jats:italic>where each cell contains a subset of {1,\u2026,<jats:italic>n<\/jats:italic>} is a (<jats:italic>\u03b2n<\/jats:italic>,<jats:italic>\u03b2n, \u03b2n<\/jats:italic>)-array if each symbol occurs at most<jats:italic>\u03b2n<\/jats:italic>times in each row and column and each cell contains a set of size at most<jats:italic>\u03b2n<\/jats:italic>. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants<jats:italic>\u03b1<\/jats:italic>,<jats:italic>\u03b2<\/jats:italic>&gt; 0 such that, for every positive integer<jats:italic>n<\/jats:italic>, if<jats:italic>P<\/jats:italic>is an<jats:italic>\u03b1<\/jats:italic>-dense<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic>partial Latin square,<jats:italic>A<\/jats:italic>is an<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n (\u03b2n, \u03b2n, \u03b2n)<\/jats:italic>-array, and no cell of<jats:italic>P<\/jats:italic>contains a symbol that appears in the corresponding cell of<jats:italic>A<\/jats:italic>, then there is a completion of<jats:italic>P<\/jats:italic>that avoids<jats:italic>A<\/jats:italic>; that is, there is a Latin square<jats:italic>L<\/jats:italic>that agrees with<jats:italic>P<\/jats:italic>on every non-empty cell of<jats:italic>P<\/jats:italic>, and, for each<jats:italic>i<\/jats:italic>,<jats:italic>j<\/jats:italic>satisfying 1 \u2264<jats:italic>i<\/jats:italic>,<jats:italic>j<\/jats:italic>\u2264<jats:italic>n<\/jats:italic>, the symbol in position (<jats:italic>i<\/jats:italic>,<jats:italic>j<\/jats:italic>) in<jats:italic>L<\/jats:italic>does not appear in the corresponding cell of<jats:italic>A<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s096354831800055x","type":"journal-article","created":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T13:51:08Z","timestamp":1550670668000},"page":"675-695","source":"Crossref","is-referenced-by-count":3,"title":["Restricted completion of sparse partial Latin squares"],"prefix":"10.1017","volume":"28","author":[{"given":"Lina J.","family":"Andr\u00e9n","sequence":"first","affiliation":[]},{"given":"Carl Johan","family":"Casselgren","sequence":"additional","affiliation":[]},{"given":"Klas","family":"Markstr\u00f6m","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,2,20]]},"reference":[{"key":"S096354831800055X_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00354-8"},{"key":"S096354831800055X_ref19","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1016\/j.disc.2011.10.025","article-title":"Constrained completion of partial Latin squares","volume":"312","author":"Denley","year":"2012","journal-title":"Discrete Math"},{"key":"S096354831800055X_ref8","first-page":"27","article-title":"Certain properties of nonnegative matrices and their permanents","volume":"211","author":"Br\u00e8gman","year":"1973","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S096354831800055X_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90092-7"},{"key":"S096354831800055X_ref25","first-page":"90","article-title":"Unavoidable arrays","volume":"5","author":"Markstr\u00f6m","year":"2009","journal-title":"Contrib. Discrete Math"},{"key":"S096354831800055X_ref18","first-page":"127","author":"Daykin","year":"1984"},{"key":"S096354831800055X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90075-1"},{"key":"S096354831800055X_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)E0206-W"},{"key":"S096354831800055X_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2017.04.005"},{"key":"S096354831800055X_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.01.019"},{"key":"S096354831800055X_ref27","first-page":"77","article-title":"Latin squares with prescriptions and restrictions","volume":"51","author":"\u00d6hman","year":"2011","journal-title":"Austral. J. Combin"},{"key":"S096354831800055X_ref24","doi-asserted-by":"crossref","first-page":"P2","DOI":"10.37236\/5675","article-title":"Completing partial Latin squares with one nonempty row, column, and symbol","volume":"23","author":"Kuhl","year":"2016","journal-title":"Electron. J. Combin"},{"key":"S096354831800055X_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-011-0106-5"},{"key":"S096354831800055X_ref20","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1960.11992032"},{"key":"S096354831800055X_ref28","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0042361-0"},{"key":"S096354831800055X_ref17","doi-asserted-by":"crossref","first-page":"R47","DOI":"10.37236\/1073","article-title":"Latin squares with forbidden entries","volume":"13","author":"Cutler","year":"2006","journal-title":"Electron. J. Combin"},{"key":"S096354831800055X_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.21355"},{"key":"S096354831800055X_ref12","unstructured":"[12] Chetwynd, A. G. and H\u00e4ggkvist, R. (1984) Completing partial n \u00d7 n Latin squares where each row, column and symbol is used at most cn times. Research report, Department of Mathematics, Stockholm University."},{"key":"S096354831800055X_ref23","unstructured":"[23] H\u00e4ggkvist, R. Personal communication."},{"key":"S096354831800055X_ref1","doi-asserted-by":"crossref","first-page":"R56","DOI":"10.37236\/780","article-title":"Completing partial Latin squares with two filled rows and two filled columns","volume":"15","author":"Adams","year":"2008","journal-title":"Electron. J. Combin"},{"key":"S096354831800055X_ref2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-47.3.507"},{"key":"S096354831800055X_ref3","unstructured":"[3] Andr\u00e9n, L. J. (2010) On Latin squares and avoidable arrays. Doctoral thesis, Ume\u00e5 University."},{"key":"S096354831800055X_ref11","first-page":"257","article-title":"Avoidable partial Latin squares of order 4m + 1","volume":"95","author":"Cavenagh","year":"2010","journal-title":"Ars Combinatoria"},{"key":"S096354831800055X_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000570"},{"key":"S096354831800055X_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.10.028"},{"key":"S096354831800055X_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199708)25:4<257::AID-JGT3>3.0.CO;2-J"},{"key":"S096354831800055X_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511984068"},{"key":"S096354831800055X_ref30","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.37236\/1629","article-title":"A generalization of transversals for Latin squares","volume":"2","author":"Wanless","year":"2002","journal-title":"Electron. J. Combin"},{"key":"S096354831800055X_ref29","first-page":"155","article-title":"A new construction for Latin squares, I: Proof of the Evans conjecture","volume":"11","author":"Smetaniuk","year":"1981","journal-title":"Ars Combinatoria"},{"key":"S096354831800055X_ref21","author":"Gustavsson","year":"1991"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831800055X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,28]],"date-time":"2020-11-28T06:00:50Z","timestamp":1606543250000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831800055X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,20]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S096354831800055X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831800055x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,20]]}}}