Existence Of A Generalized Kirkman Square GKS(n+1, 3n)

Let n, s be two positive integers, X is a 3n-set. A generalized Kirkman square of side s and order 3n on X, or more briefly, a GKS(s, 3n), is an s×s array, such that(1) each cell either is empty or else contains an unordered 3-subset from X;(2) each row and column is Latin (that is, every element of X is in precisely one cell of each row and each column);(3) every unordered pair of X is in at most one cell of the array.Recently, Etzion [9] has found a method of constructing optimal doubly constant weight codes by generalized Kirkman squares. He put forward one study question: establish the existence of a generalized Kirkman square GKS(s, 3n).A trivial GKS(s,3n) is a GKS(s, 0) having X = (?) and consisting of an s×s array of empty cells. A necessary condition on s and n for the existence of a nontrivial GKS(s,3n) is that 0 < n≤s≤3n-1/2. In the extreme case, when s = 3n-1/2 and n≡1(mod 2), a GKS(3n-1/2,3n) is also known as a Kirkman square of side 3n-1/2 and order 3n. The existence question of Kirkman squares is almost completely settled by Colbourn,Lamken, Ling and Mills [6]. In the other extreme case, namely when s = n, Phillips, Wallis [11] and Soicher [13] established the existence of GKS(n, 3n)s.We research the existence question of generalized Kirkman squares of order 3n when s = n + 1. We show that there exists a GKS(n + 1,3n) for any positive integer n > 6 with at most 4 possibly exceptions for n. This is accomplished by describing direct constructions for GKS(n + 1, 3n)s for small n (section 2) and by the use of recursive constructions (section 3).