Universal tilings and universal (0,1)-matrices (Q1078571)

A periodic edge-to-edge tiling of the plane by black and white squares is called k-universal if it contains all possible (k\(\times k)\)-blocks of black and white tiles. The paper discusses the problem of finding the k- universal tilings with the smallest fundamental block. This problem is shown to be related to the problem of finding the k-universal (0,1)- matrices of minimal size; here, k-universal means that any (0,1)-matrix of size \(k\times k\) occurs as a submatrix. It is proved that there are k- universal matrices of size \(k2^{k/2}\times k2^{k/2}\) or \((3k+1)2^{(k-3)/2}\times (3k-1)2^{(k-3)/2}\) if k is even or odd, respectively. Then, the 3-universal (10\(\times 8)\)-matrix is used to construct a 3-universal tiling of the plane.