Trading signed designs and some new 4-(12, 5, 4) designs (Q1358668)

The authors investigate a method of generating \(t\)-\((v,k,\lambda)\) designs by the use of trades incorporated into a local search algorithm. \(t\)-designs here are represented as solutions to the system of linear equations \(P^v_{tk}F = \lambda e_t\), where \(P^v_{tk}\) is the \((^v_t) \times (^v_k)\) \((0,1)\) matrix whose rows and columns are indexed by the \(t\)- and \(k\)-subsets (respectively) of a set of \(v\) elements, and \(e_t\) is the \((^v_t)\)-dimensional all ones vector. This is the well-known \(A_{tk}\) matrix representation first used by \textit{E. S. Kramer} and \textit{D. M. Mesner} in [Discrete Math. 15, 263-296 (1976; Zbl 0362.05049)]. An integral solution of this equation is called a \(t\)-\((v,k,\lambda)\) signed design. A nonnegative integral solution is called a \(t\)-\((v,k,\lambda)\) design. An integral solution for \(\lambda = 0\) is called a \(t\)-\((v,k)\) trade. If the components of a solution belong to \(\{0,-1,1\}\) then the (signed) design or trade is called simple, otherwise it is called a (signed) design or trade with repeated blocks. For any \(t\) and \(k = t+1\), any simple \(t\)-\((v,k)\) trade is called minimal if it has \(2^{t+1}\) non-zero components. The local search algorithm presented in this paper begins with a signed design \(F\), and then produces augmented designs \(F + T\) for selected minimal trades \(T\). Using a set of cost functions the search is guided towards a global minimum which represents a \(t\)-\((v,k,\lambda)\) design. The technique was applied to the case of \(4\)-\((12,5,4)\) designs to generate 20 new, mutually non-isomorphic simple designs in addition to the 30 that were already known. An effective invariant based on minimal trades is used to distinguish most of these 50 designs. Minimal trades also provide a new method for representing \(t\)-designs. Finally, \(4\)-\((12,5,4)\) designs with repeated blocks are investigated. Here the support size of a design, denoted by \(b^*\), is defined to be the number of distinct blocks in the design. A \(4\)-\((12,5,4)\) design for every support size \(b^*\) in the range \(344 \leq b^* \leq 396\) is constructed. It is conjectured that the minimal possible value of \(b^*\) for this design type is 344.