Pushing the Limits of Computational Combinatorial Constructions

A combinatorial $t$-$(v,k,\lambda )$ design $(V,𝒟)$ is a set $V$ consisting of $v$ points together with a set $𝒟$ of $k$-subsets of $V$ called blocks such that each $t$-subset of $V$ is contained in exactly $\lambda$ blocks, see e.g. [1, 2] or [7]. The $q$-analogs of combinatorial designs are called subspace designs, see [5] for an introduction and overview.

It is well known that a $t$-$(v,k,\lambda )$ design $(V,𝒟)$ is also an $s$-$(v,k,{\lambda }_s)$ design for $0\le s\le t$ where

In particular, ${\lambda }_0$ is the number of blocks of the design and ${\lambda }_1$ is the number of blocks each point is contained in, which is called the replication number. It is also well known that for a $t$-$(v,k,\lambda )$ design the number of blocks which contain a given $i$-set of points and are disjoint to a given $j$-set of points is equal to

see e.g. [7, II.4.2, p. 80].

The $v\times {\lambda }_0$ point-block incidence matrix $N$ of a $t$-$(v,k,\lambda )$ design $(V,𝒟)$ is defined by

for $P\in V$ and $B\in 𝒟$. Bose [4] showed for the point-block incidence matrix $N$ of a $2$-$(v,k,\lambda )$ design the equation

where $I$ is the $v\times v$ identity matrix and $J$ is the $v\times v$ all-ones matrix.

For a general $t$-$(v,k,\lambda )$ design with $t\ge 2$, the $\left(\genfrac{}{}{0pt}{}{v}{e}\right)\times {\lambda }_0$ higher incidence matrix $N^{(e)}$ for $e\le k$ is defined by

for $E\in \left(\genfrac{}{}{0pt}{}{V}{e}\right)$ and $B\in 𝒟$. The $\left(\genfrac{}{}{0pt}{}{v}{s}\right)\times \left(\genfrac{}{}{0pt}{}{v}{e}\right)$ incidence matrix $W^{(se)}$ between $s$-subsets and all $e$-subsets of $V$ is defined by

for $S\in \left(\genfrac{}{}{0pt}{}{V}{s}\right)$ and $E\in \left(\genfrac{}{}{0pt}{}{V}{e}\right)$. Wilson [18] showed for $e+f\le t$ the equation

Note that $N^{(e)}{(N^{(f)})}^{\top }$ contains in the row labeled by the $e$-subset $E$ and in the column labeled by the $f$-subset $F$ the number of blocks of the design which contain both $E$ and $F$. It is clear that this number is ${\lambda }_{e+f-\mu }$ with $\mu =\mathrm{\#}(E\cap F)$, i. e.

Also in [18], Wilson proved among others the equation

For $e=1$ and $i=0$ equation (3) simply states that each block of the design contains $k$ points.

The use of tactical decompositions in design theory has been initiated by Dembowski [9], see also [10] and Beutelspacher [3, pp. 210–220]. Dembowski’s main interest was to use tactical decompositions to study properties of symmetric designs. From an algorithmic point of view, tactical decompositions were first used by Janko and Tran Van Trung [11] to construct symmetric $(78,22,6)$ designs. Their method was picked up and generalized in numerous papers, see [6, 8, 14] to name just a few. In [17] the use of tactical decompositions has been generalized to subspace designs.

Dembowski [9, 10] studied tactical decompositions of incidence structures from group actions, see also Beutelspacher [3, pp. 210–220].

Let $(V,𝒟)$ be a $2$-$(v,k,\lambda )$ design invariant under some group $G$. The action of $G$ partitions $V$ into orbits ${𝒫}_1,\mathrm{\dots },{𝒫}_m$ and $𝒟$ into orbits ${ℬ}_1,\mathrm{\dots },{ℬ}_n$. Let $N$ be the point-block incidence matrix of $(V,𝒟)$ and for $i\in \{1,\mathrm{\dots },m\}$ and $j\in \{1,\mathrm{\dots },n\}$ let $N_{i,j}$ be the submatrix of $N$ whose rows are assigned to the elements ${𝒫}_i$ and whose columns to the elements of ${ℬ}_j$. Then $N_{i,j}$ has a constant number of ones in each row and a constant number of ones in each column. Such a decomposition of $N$ into submatrices $N_{i,j}$ is called tactical.

If we replace for all $i,j$ the submatrix $N_{i,j}$ by the number of ones in each row we get an $(m\times n)$-matrix $\rho$, and if we replace the submatrix $N_{i,j}$ by the number of ones in each column we get an $(m\times n)$-matrix $\kappa$. The matrices $\rho$ and $\kappa$ are both called tactical decomposition matrix. In [9] the following properties of $\rho$ and $\kappa$ and the matrices $P=\text{diag}(\mathrm{\#}{𝒫}_i)$ and $B=\text{diag}(\mathrm{\#}{ℬ}_i)$ are shown:

The general approach outlined by Janko and Tran Van Trung is to first enumerate all tactical decomposition matrices of designs with prescribed automorphisms up to permutations of rows and columns. For this, Dembowski [9] has given powerful constraints for a matrix to be a tactical decomposition of the point-block incidence matrix of a $2$-design. In a second step, all remaining tactical decomposition matrices are expanded – if possible – to point-block incidence matrices of designs.

Compared with the well-known method of Kramer and Mesner [13] which also restricts the search space to designs with prescribed automorphisms, the method of Janko and Tran Van Trung has the advantage that it is not necessary to compute all orbits of $k$-subsets of $V$ and therefore allows the search for $2$-$(v,k,\lambda )$ designs with larger $k$ and smaller automorphism group. The drawback however is that it does not reduce the search space if the prescribed group of automorphisms is point-transitive, and that it seemed to be restricted to $2$-designs for a long time.

In recent years two generalizations to $t$-designs for $t\ge 2$ have been published.

The first generalization in [14, 15, 16] gives constraints for the tactical decomposition of the point-block incidence matrix of a $t$-design of general strength $t\ge 2$:

The second generalization in [12] defines higher tactical decomposition matrices and shows the Wilson’s equations can be generalized to these higher tactical decomposition matrices.

For $x\in \{0,\mathrm{\dots },v\}$, let ${𝔓}_x$ be a partition of the set $\left(\genfrac{}{}{0pt}{}{V}{x}\right)$. The part of ${𝔓}_x$ containing some $X\in \left(\genfrac{}{}{0pt}{}{V}{x}\right)$ will be denoted by $[X]$. We call $({𝔓}_0,\mathrm{\dots },{𝔓}_v)$ a tactical sequence of partitions on $V$ if for all $x,y\in \{0,\mathrm{\dots },v\}$ with $x\le y$ and for all $[X],𝒳\in {𝔓}_x$ and $[Y],𝒴\in {𝔓}_y$, the numbers

are well-defined, i. e. they do not depend on the choice of the representative $X$ of $[X]$ nor of the representative $Y$ of $[Y]$. In this case, the above defined numbers yield matrices $R^{(xy)},K^{(xy)}\in {\mathbb{Z}}^{{𝔓}_x\times {𝔓}_y}$. A common source of tactical sequences of partitions are permutation groups $G\le S_V$, where for all $x\in \{0,\mathrm{\dots },v\}$ the partition ${𝔓}_x$ is the set of orbits of the induced action of $G$ on $\left(\genfrac{}{}{0pt}{}{V}{x}\right)$.

In the following, a tactical sequence $({𝔓}_0,\mathrm{\dots },{𝔓}_v)$ of partitions on $V$ is fixed. The matrices $R^{(xx)}$ and $K^{(xx)}$ are $\mathrm{\#}{𝔓}_x\times \mathrm{\#}{𝔓}_x$ identity matrices. The matrices $R^{(0x)}$ and $K^{(0x)}$ are of size $1\times \mathrm{\#}{𝔓}_x$, where all entries of $K^{(0x)}$ are $1$, and $R^{(0x)}$ contains the part sizes, i. e. $R_{\{\mathrm{\varnothing }\},𝒳}^{(0x)}=\mathrm{\#}𝒳$.

Let $(V,𝒟)$ be $t$-$(v,k,\lambda )$ design with $t\le k\le v-t$, such that the block set is the union of parts in ${𝔓}_k$, i. e. $𝒟=\bigcup 𝔅$ with $𝔅\subseteq {𝔓}_k$.

For $x\in \{0,\mathrm{\dots },k\}$ we define the tactical decomposition matrices ${\rho }^{(x)},{\kappa }^{(x)}\in {\mathbb{Z}}^{{𝔓}_x\times 𝔅}$ via

By the properties of the fixed tactical sequence $({𝔓}_0,\mathrm{\dots },{𝔓}_v)$ of partitions on $V$, this definition does not depend on the choice of the representatives. Note that ${\rho }^{(x)}$ is the restriction of $R^{(xk)}$ to the columns whose labels are contained in $𝔅$. In particular, ${\rho }^{(0)}$ and ${\kappa }^{(0)}$ are of size $1\times \mathrm{\#}𝔅$, where all entries of ${\kappa }^{(0)}$ are $1$, and ${\rho }^{(0)}$ contains the sizes of the block parts.

In [12] the following theorem has been proved for these higher tactical decomposition matrices.

It should be noted that the above theorem has a $q$-analog version for subspace designs.

In the working group an introduction to tactical decomposition matrices has been given. This was followed by a long discussion in which the two generalizations were compared and where it was attempted to derive the first generalization from the second. As a result, the exact relation of the two generalizations could not be determined easily and will be subject of future research work.

Next, algorithmic use of the second generalization was studied. The participants of the working group agreed that the approach by Janko and Tran van Trung might be generalized to higher tactical decompositions, however its applicability will be restricted to a very specific set of parameters of combinatorial designs and choice of prescribed automorphism groups.

As a followup, research groups from Zagreb and Bayreuth are planning to write a proposal for a joint research project to develop a practical algorithm based on higher tactical decomposition matrices.

Another topic of the working group was the indexing step of the Janko-Tran van Trung algorithm and possible generalizations.

Finally, for graphs and hypergraphs the concept of tactical decomposition matrices is known as equitable partitions. Main contributions for these have been given by the research group in Novosibirsk. The presentation of results on equitable partitions lead to surprising connections to the so called Hartman’s conjecture in design theory. This was explored and further research on this connection seems to be promising.