HOPs and COPs: Room frames with partitionable transversals (Q1970567)

Consider a set \(S\). Let \(\{S_1,\dots, S_n\}\) be a partition of \(S\). An \(\{S_1,\dots, S_n\}\)-Room frame is an \(|S|\times|S|\) array, \(F\), index by \(S\), satisfying that (1) every cell of \(F\) either is empty or contains an unordered pair of elements in \(S\), (2) the subarrays \(S_i\times S_i\) are empty for all \(i\), (3) each element \(x\not\in S_i\) occurs once in row (or column) \(s\), for any \(s\in S_i\), and (4) the pairs occurring in \(F\) are \(\{s,t\}\), where \(s\) and \(t\) belong to different \(S_i\)'s. A complete transversal is a set \(T\) of \(|S|\) filled cells in \(F\) (one in each row and column) such that every element of \(S\) is in exactly two cells of \(T\). \(T\) is called an ordered transversal if the cells of \(T\) are ordered so that every element of \(S\) occurs once as a first coordinate and once as a second coordinate. \(T\) is called partitionable if \(|S|\) is even and \(|T|\) can be partitioned into two equal parts \(T_1\) and \(T_2\) such that every element of \(S\) appears once in \(T_1\) and once in \(T_2\). In the above definitions, if we replace \(S\) by \(S- S_i\), then they become definitions for holey transversal, ordered holey transversal, and partitionable holey transversal with respect to the hole \(S_i\). In this paper, the authors construct ordered partitionable complete transversals and ordered partitionable holey transversals with direct and recursive methods.