Towards the spectrum of Room squares with subsquares
Let \(S\) be a set of \(n+1\) symbols. A Room square of side \(n\) is an \(n\times n\) array \(F\) satisfying the following: (1) Every cell of \(F\) contains either nothing or an unordered pair of different symbols in \(S\). (2) Every symbol of \(S\) apperas exactly once in each row and each column of \(F\). (3) Every pair of different symbols in \(S\) appears exactly once in \(F\). Let \(T\) be a subset of \(S\) of cardinality \(s+1\). An \((n,s)\)-IRS (incomplete Room square) is an \(n\times n\) square array \(F\) satisfying (1) and the following: (4) There is an empty \(s\times s\) subarray \(G\) of \(F\). (5) Each symbol in \(S\backslash T\) appears exactly once in each row and each column of \(F\). (6) Each symbol in \(T\) appears exactly once in each row and each column not meeting \(G\), but not in any row or column meeting \(G\). (7) Every pair in \((S\times S)\backslash(T\times T)\) appears exactly once in \(F\). Note that \(G\) can be filled in with any Room square of side \(s\) on symbol set \(T\), thereby obtaining a Room square of side \(n\) containing a subsquare of side \(s\). R. J. Collens and R. C. Mullin pointed out that the existence of an \((n,s)\)-IRS requires that \(n\) and \(s\) are odd and \(n\geq 3s+2\) and conjectured that this necessary condition is also sufficient with the single exception \((n,s)\neq(5,1)\). In this paper, authors proved that this conjecture is true for \(s\geq 393\). Since J. H. Dinitz and D. R. Stinson proved previously that the conjecture is true for \(3\leq s\leq 15\), the remaining open case is \(17\leq s\leq 391\).
scientific article; zbMATH DE number 165163
scientific article