Omnimosaics

Abstract

An {\it omnimosaic} $O(n,k,a)$ is defined to be an $n\times n$ matrix, with entries from the set $\mathcal{A}=\{1,2,\dot{.}.,a\}$, that contains, as a submatrix, each of the $a^{k^2}$ $k\times k$ matrices over $\mathcal{A}$. We provide constructions of omnimosaics and show that for fixed $a$ the smallest possible size $\omega (k,a)$ of an $O(n,k,a)$ omnimosaic satisfies \[\frac{ka^{k/2}}{e}\le ω(k,a)\le \frac{ka^{k/2}}{e}(1+o(1))\] for a well-specified function $o(1)$ that tends to zero as $k\to \infty$.

arXiv comment19 pages