A $(n,n/2,\lambda)$ block-design is a family $A_1,...,A_K$ of subsets of $[n]$ such that $|A_i|=n/2$ and for every $1 \leq i < j \leq n$ it holds that $\#\{1 \leq k \leq K : i,j \in A_k \} = \lambda$. My question is: What is the minimal $K$ for which such a design exists?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ If you fix both $n$ and $\lambda$, this determines $K$ if the design exists. If you fix $n$ and let $\lambda$ vary, this requires you to be able to determine whether designs with particular parameters exist, which is hard in general. $\endgroup$– Douglas ZareApr 2, 2016 at 18:39
-
$\begingroup$ To clarify Douglas's comment, K will be $\lambda(2n-2)/(n/2-1)$. However, even if K is a positive integer, that is not enough to guarantee the existence of the design with the desired parameters. Gerhard "Has Designs On Some Designs" Paseman, 2016.04.02. $\endgroup$– Gerhard PasemanApr 2, 2016 at 19:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You can take all of the $2$-subsets of $[4]$ to get a $(4,2,1)$ design with $6$ blocks. This is the smallest possible number of blocks, but maybe you would want to excuse it for being trivial. There is also an $(8,4,3)$ design with $14$ blocks. I'm not sure if there is anything in between.
$\begingroup$
$\endgroup$
$K=10$. The ten triangles in the image below form the blocks of a $2\text{-}(6,3,2)$ design.
Image from here: https://math.stackexchange.com/a/366455/65
This is optimal if you insist that your design is not $\binom{[n]}{n/2}$.
We have $nr=Kn/2$ where $r$ is the replication number. So K is even.
For $K=8,4,2$, there are no solutions $(n,\lambda)\in \mathbb N^2$ to $K=\frac{2\lambda (n-1)}{n/2-1}$. For $K=6$, you have $n=4$, which gives the trivial case.
Or you could look up the Design Database.
answered Apr 23, 2016 at 17:01