Perfect Mendelsohn Designs With Block Size Four

Abstract

Let $v$, $k$, and $\lambda$ be positive integers. A $(v,k,\lambda )$-Mendelsohn design (briefly $(v,k,\lambda )$-MD) is a pair $(X,B)$ where $X$ is a $v$-set (of points) and $B$ is a collection of cyclically ordered $k$-subsets of $X$ (called blocks) such that every ordered pair of points of $X$ are consecutive in exactly $\lambda$ blocks of $B$. A set of $\delta$ distinct elements $\{a_1,a_2,\dots ,a_{\delta }\}$ is said to be cyclically ordered by $a_1<a_2<\dots <a_k<a_1$ and the pair $a_i,a_{i+t}$ are said to be $t$-apart in a cyclic $k$-tuple $(a_1,a_2,\dots ,a_k)$ where $i+t$ is taken modulo $k$. If for all $t=1,2,\dots ,k-1$, every ordered pair of points of $X$ are $t$-apart in exactly $\lambda$ blocks of $B$, then the $(v,k,\lambda )$-MD is called a perfect design and is denoted briefly by $(v,k,\lambda )$-PMD. A necessary condition for the existence of a $(v,k,\lambda )$-PMD is $\lambda v(v-1)\equiv 0$ (mod $k$). In this paper, we shall be concerned mainly with the case where $k=4$. It will be shown that the necessary condition for the existence of a $(v,4,\lambda )$-PMD, namely, $\lambda v(v-1)\equiv 0$ (mod $4$), is also sufficient, except for $v=4$ and $\lambda$ odd, $v=8$ and $\lambda =1$, and possibly excepting $v=12$ and $\lambda =1$. Apart from the existence of a $(12,4,1)$-PMD, which remains very much in doubt, the problem of existence of $(v,4,\lambda )$-PMDs is now completely settled.