An extemal combinatorial design question. "Weak" steiner stystems.

109 Views Asked by At

A Steiner system $S(t,k,\nu)$ is a collection $X$ of $\nu$ points and a collection of subsets of $X$ of size $k$ (frequently called blocks) such that each $t$ element subset of $X$ occurs in exactly $1$ of these blocks.

Steiner systems do not always exist, but it would be nice to find systems that don't necessarily satisfy all of the properties. Specifically, a collection of blocks for some set $X$ such that every $t$ element subset occurs $\textbf{at most}$ once. Until I find that this idea already has a name, I will refer to such a system as a weak Steiner system.

Let's look at an example to solidify this idea. There does not exist a Steiner system $S(2,3,5)$ since Steiner triple systems (where $t=2$ and $k=3$) exist if and only if $\nu=1,3\pmod 6$. However, we can look at weak Steiner systems in this case. Denote the elements of $X$ by $\{1,2,3,4,5\}$. Take, as our collection of blocks, $\{1,2,3\}$. In this case, only the single block $\{1,2,3\}$. Then this is a weak Steiner system for the case $(t=2,k=3,\nu=5)$. This is, however, not a maximal weak Steiner system. Indeed, I can take as my collection of blocks $\{1,2,3\},\{4,5,6\}$. This too is a weak Steiner system, but with more blocks. This design is maximal, and that fact can be quickly verified through a case by case argument. In this case, I use the notation $D(2,3,5)=2$. This means that the maximum number of blocks possible in a weak Steiner system (for these values of $t,k,\nu$) is $2$.

One more example, take $X$ to be the $6$ element set and denote its elements $\{1,2,3,4,5,6\}$. I claim that $D(2,3,6)=4$. Observe first that $X$ contains exactly $\binom{6}{2}=15$ distinct doubles, and each triple/block contains exactly $\binom{3}{2}=3$ doubles. Hence, $D(2,3,6)\le 5$. Since we know that a Steiner triple system does not exist in this case, we can conclude that $D(2,3,6)\le 4$. Take as a collection of blocks $\{1,2,3\},\{1,4,5\},\{2,4,6\},\{3,5,6\}$ and observe that no double occurs more than once. Hence, $D(2,3,6)=4$.

I am interested in determining this number for various values of $t,k,\nu$. In the case when $t=2$, there is a generalization of this concept called the $H$ packing number of a graph $G$. A packing of a graph $G$ is a collection of subgraphs of $G$ that are isomorphic to $H$ such that the collection of subgraphs are $\textbf{edge disjoint}$. The most number of subgraphs isomorphic to $H$ in a packing is the packing number, denoted $P(H,G)$. Specifically, when $t=2$, the packing number $P(K_k,K_\nu)$ is exactly the number I have been looking for, $D(2,k,\nu)$. However, this, as far as I know, does not generalize to higher values of $t$, say $t=3$.

My question here is really a reference request. Has this question of determining the most number of blocks in a "weak Steiner system" appeared before? Has the notion of a "weak Steiner system" been researched before? What work has been done on this when $t\ge 3$? Any nudge in the right direction would be helpful to me.

Here is a relevant question that pertains to the case when $t=2$. Here is a link to a paper where the $H$-packing number is discussed and defined.