Pairwise balanced designs with $r=\lambda^{2}$

Question

A while ago I asked how to construct an infinite family of $(v,b,r,k,\lambda)$-designs satisfying $r=\lambda^{2}$ and got very good answers from Yuichiro Fujiwara and Ken W. Smith.

Now I'd like to up the ante and to generalize the question to $(r,\lambda)$-designs. Formally, we are talking here about a family $D$ of subsets of $\{1,2,\ldots,v\}$ such that:

(a) Each $i \in \{1,2,\ldots,v\}$ belongs to $r$ sets in $D$.

(b) Every two distinct $i,j \in \{1,2,\ldots,v\}$ belong together to $\lambda$ sets in $D$.

I am trying to find examples with $r=\lambda^{2}$, which is more difficult than in the case of $(v,k,\lambda)$ designs because this is more off the beaten path, so even stand-alone examples will be greatly appreciated.

P.S. As in the previous question, I require at least one pair of disjoint blocks, so most constructions based on symmetric designs will not apply here.

Answer 1

Assuming you meant $r = \lambda^2$ (and also assuming you don't want repeated blocks), a proper approach might be to poke around the properties of $(r,\lambda)$-designs and their constructions to give necessary and sufficient conditions for the existence of such designs. But if you only need infinitely many nontrivial examples for various mixes of block sizes, you can construct them by generalizing the previous method as follows:

To obtain an $(r,\lambda)$-design with the desired property, you take a union of disjoint $S(2,k,v)$s like the previous method. But this time, you need more than one block size. I assume that you're familier with combinatorics and can prove the existence of set $\mathcal{S}$ of disjoint $S(2,k,v)$s with fairly large cardinality $\vert \mathcal{S} \vert$ on your own.

If you take a union of $x_i$ disjoint $S(2,k_i,v)$s, the resulting set forms the block set $\mathcal{B}$ of an $(r,\lambda)$-design with

$$r = \sum_i \frac{x_i(v-1)}{k_i-1}$$ and $$\lambda = \sum_i x_i.$$ So you only need to find suitable $x_i$ that satisfy $$\sum_i \frac{x_i(v-1)}{k_i-1} = \left(\sum_i x_i \right)^2$$ while keeping in mind that you should find $x_i$ disjoint $S(2,k_i,v)$s for each $i$. This way, in principle, you should be able to construct an $(r,\lambda)$-design with $r = \lambda^2$ and your favorite block size variation. I doubt this method covers all the parameters satisfying some necessary conditions you can derive by a simple counting argument, though. I didn't even do a back-of-the-envelop calculation.

Anyway, to illustrate how this construction works, consider the case when you want only block size, say, $3$ and $5$. Then the sums in the equation only have two terms each:

$$\frac{x_0(v-1)}{4}+\frac{x_1(v-1)}{2} = (x_0 + x_1)^2.$$

You need integer solutions while ensuring you sure have the specified numbers of disjoint guys. But it's not that difficult. For example, take $x_0 = \frac{2(v-1)}{9}$ and $x_1 = \frac{v-1}{9}$. I pulled these numbers off the top of my head, but this should be an example of solutions. You can check it or solve the equation in a general way for yourself. Anyway, all you have to do now is to see if there are $\frac{2(v-1)}{9}$ disjoint $S(2,5,v)$s and $\frac{v-1}{9}$ disjoint $S(2,3,v)$s. But this is almost trivially true because $x_0, x_1 \ll v$.

For instance, for $k=3$ you can use (part of) a large set of Steiner triple systems, which contain $v-2$ disjoint $S(2,3v)$s. For $k=5$, because you only need to find $\frac{2(v-1)}{9}$ disjoint $S(2,5,v)$s among the humongous numer ${{v}\choose{5}}$ of all $5$-tuples, you should be able to find them quite easily. For example, you can use the probabilistic method to show that if $v$ is sufficiently large, whatever $S(2,k,v)$ you have, you can find $\frac{2(v-1)}{9}$ isomorphisms (i.e., permutations of points) that lead to mutually disjoint designs. My quick calculation says you can easily find $v$ disjoint-inducing parmutations for $k \geq 5$, so gathering $\frac{2(v-1)}{9}$ disjoint $S(2,5,v)$s is no problem. Of course you can use whatever method you like to give disjoint designs. The point is that you pick small enough solutions $x_i$ (relative to $v$) so that you can find disjoint guys without a problem.

Edit: I didn't mention, but this works only when $v$ satisfies sufficient conditions for the existence of $S(2,k_i,v)$ for all $i$. So, the above example with $k_0=3$ and $k_1=5$ is implicitly assuming $v \equiv 1, 3 \pmod{6}$ and $v \equiv 1, 5 \pmod{20}$ (and $v$ large enough).

Answer 2

With blocks allowed to repeat and block sizes allowed to differ, you should be able to do lots of things if you do not insist that the number of points be small. I am about to add another answer with a different perspective. The point of this on is that a $(v,b,r,k,\lambda)$ is an $(r,\lambda)$ design and stays so even if some points are deleted. So $(r_i,\lambda_i)$ designs with the same points can be combined to get $(\sum r_i,\sum \lambda_i)$ designs which have somewhat regular block structure.

1) You say that you don't want to just repeat a symmetric design $r$ times because you want at least some disjoint blocks. But you can permute the underlying set. A small example is the Fano plane

013 124 235 346 450 561 602

repeat the blocks three times each but in the third copy swap 0 and 1 to get

013 024 235 346 451 560 612

now the blocks 124 and 560 are disjoint.

I was being lazy there anyway, The 35 triples from a 7-set can be partitioned into 5 groups of 7 with each group a Fano plane, so use three groups to have an honest $(v,b,r,k,\lambda)=(7,21,9,5,3)$ design with distinct blocks.

2) The complements of the lines in a Fano plane gives $(r,\lambda)=(4,2).$ Just taking the pairs gives $(r,\lambda)=(6,1)$ So the anti-lines once and the pairs twice each is $(16,4)$

3) To have a $(v,k,\lambda)$ BIBD is it necessary that $b=\frac{v(v-1)\lambda}{k(k-1)}$ and $r=\frac{(v-1)\lambda}{k-1}$ be integers. That is not sufficient in all cases but for each $k$ it is so long as $v$ is large enough (which is perhaps not all that large, and pretty soon there are (super)exponentially many non-isomorphic ones IIRC). I only know the ancient results that those two conditions are sufficient for $\lambda=1,2$ and $k=3,4,5$ with the one exception of $(v,k,\lambda)=(15,5,2).$ First let's work with $k=5.$ So for every $m \gt 1$ there are BIBDs with these $(v,r,k,\lambda)$ values:

$(20m+1,5m,5,1)$ ,$(20m+5,5m+1,5,1)$,$(10m+1,5m,5,2)$ and $(10m+5,5m+2,5,2).$

So we have a $(55,27,5,2)$ design. The projective plane over $GF_7$ is a $(57,8,8,1)$ design. Delete two points to get blocks of sizes $6,7,8$ but still $(r,\lambda)=(8,1).$ Now we can take $p$ copies of the first design and $q$ of the second to get $(r,\lambda)=(27p+8q,2p+q).$ Can we have $(2p+q)^2=27p+8q?$ Yes, if $q=4-2p+\sqrt{11p+16}.$ So $(p,q)=(3,5)$ gives a design with $v=55,r=121,\lambda=11.$ The repeat numbers are low enough to comfortably have distinct blocks.

That was a rather haphazardly constructed example. I just wanted to get away from $\lambda=1.$ I imagine would could do all manner of things with other $v$. I'll stick with $v=55.$ There is not a design with $(v,k,\lambda)=(55,4,1)$ but there is one with $(v,r,k,\lambda)=(55,36,4,2)$ so we are sure that it is not just two $\lambda=1$ designs. We could take 9 copies of this $(r,\lambda)=(36,2)$ design. More fun is one copy of that design along with $8$ copies of the mutilated projective plane to get a total of $(r,\lambda)=(36+8\cdot 8,2+8 \cdot 1)=(100,10).$ Also possible is two copies of the $(r,k,\lambda)=(36,4,2)$, two mutilated projective planes and four copies of the $(r,k,\lambda)=(27,5,2)$ for a total of $(r,\lambda)=(2\cdot36+2\cdot 8+4 \cdot 27,2 \cdot 2+2 \cdot 1+4\cdot2)=(196,14).$

I'll stop there but, since $55$ is of the form $6m+1$ there is a $(v,r,k,\lambda)=(55,27,3,1)$ design and of course there is the $(v,r,k,\lambda)=(55,54,2,1)$ Perusing the Google copy of the CRC handbook of combinatorial designs I see that there are also $(v,r,k,\lambda)=(56,11,11,2),(56,15,12,3))$ which could be mutilated for $v=55.$ So there may be further combinations to consider.

Here are some things I found for $v=56$:

$[0, 3, 1, [10, 100]], [4, 1, 2, [13, 169]], [0, 4, 3, [15, 225]], [6, 1, 9, [24, 576]],$

$ [0, 5, 10, [25, 625]], [0, 5, 15, [30, 900]], [6, 1, 16, [31, 961]], [0, 4, 28, [40, 1600]],$

$ [4, 1, 31, [42, 1764]], [0, 3, 36, [45, 2025]]$

The second item $[4, 1, 2, [13, 169]]$ means that 4 copies of the $(56,11,11,2)$ along with one copy of the $(56,15,12,3)$ and 2 copies of the $(56,55,2,1)$ design give $169=r=\lambda^2.$ There is no choice but to repeat the $k=2$ design however there are (according to the handbook) at least five non-isomorphic $(56,56,11,11,2)$ designs. I did not see that the mutilated projective plane was helpful for $v=56.$

Answer 3

Assuming $r=\lambda^2$, here is a stand-alone example with $r=4$: the blocks are 1234, 12, 13, 14, 23, 24, 34. Note that the blocks 12 and 34 are disjoint.

EDIT: One can extend this example to 12345, 125, 13, 14, 23, 24, 345, 5

and then to 123456, 125, 136, 14, 23, 246, 345, 56

and then to 123456, 1257, 1367, 14, 23, 2467, 3457, 56.

Answer 4

Here is a perspective different enough to merit being its own answer. Perhaps it is already familiar to you.

I find it easier to think of the equivalent dual problem: Look instead for designs where all the blocks have size $r$ and every pair intersects in $\lambda$ points. Then swap the roles of points and blocks to get what you want. In your case $r=\lambda^2$ it is useful to look at sets of planes in affine space $F_q^3$ at least for cases such as $q=2,3,4,5$ when $\lambda=q$ is a prime power.

So for $(r,\lambda)=(4,2)$ we just need some $4$-sets, each pair having intersection of size $2$. The simple example $abcd,abef$ would translate into a somewhat unsatisfactory two point example $12,12,1,1,2,2$ although this construction can make an $r,\lambda$ design with any number of points and any $r \ge \lambda$ (if we allow one point blocks and repeats.... but we won't.)

The $(r,\lambda)=(4,2)$ example of $8$ blocks made from $6$ points $a=123456, b=125, c=136, d=14, e=23, f=246, g=345, h=56$ would be dual to 6 blocks from $8$ points $abcd ,abef, aceg, adfg, abgh, acfh.$ Using binary vectors $a=xyz=000, b=001, c=010, d=011, e=100,f=101,g=110,h=111$ we see the six blocks (in the same order) are $x=0,y=0,z=0,x+y+z=0,x+y=0,x+z=0.$ We could extend this (dual) design with one or the other of the complementary blocks (planes) $adeh,bcfg$ corresponding to $y+z=0$ and $y+z=1.$ In the original design a point $7$ would go into blocks $a,d,e,h$ or the other four blocks.

I think that every nontrivial (i.e. no single point blocks) $(4,2)$ design comes from this geometry, I sketch an arguement. We could simply imagine a graph with $70$ vertices, one for each $4$-set from $\{a,b,\cdots,h\}$ each on $36$ edges connecting it to the vertices for sets sharing exactly two points with it. We simply want a (nice) clique from this graph. I think all examples up to isomorphism could be found and that $8$ is maximal. As a start (trust at your own risk) we may as well assume that two blocks (call them squares) are $abcd,abef.$ Either there is a third $abgh$, or else there are never two letters in common to three squares. In the first case we still have enough room under automorphism to assume that the fourth square (if any) is $aceg.$ At this stage the only other possible squares are $acfh/bdeg,adeh/bcfg,adfg/bceh.$, We can take up to three (one from each pair) and need to take at least two if we want (for non-triviality) to have at least one more square on each of $d,f,h.$ What if there never are two points in three common blocks? $abcd,abef,cdef$ corresponds to blocks $12,13,23$ taken twice each. That might be all that is possible if in addition any three squares are disjoint. Otherwise we could start with squares $abcd,abef,aceh$ and continue from there making sure that every two squares share a pair of points but no triple does. So the only remaining possible squares seem to be $adfh,bceg,bcfh,bdeh,cdef.$ Up to isomorphism I see four completions, one each with a total of 4,5,6,7 squares. Each does come from the affine space (again, I might be wrong.)

So for $q=2,3,4,5$ and other prime powers we can make use of $AG(3,q)=F_q^3$ which has the $q^3$ points and planes made of $q^2$ points. There are $q^2+q+1$ parallel classes (each with $q$ planes) and planes intersect in $0$ or $q$ points according as they are parallel or not. We can freely choose one (or no) planes from each parallel class and get a myriad of designs. I would expect that there are other examples for $q \gt 2$ which do not arise in this way. When $q$ is not a prime power we could still have some equations over the ring $\mathbb{Z}_q^3.$

Of course for any $q$ we can always take a point set and an initial configuration of size $q^2$ sets and then more or less randomly start selecting sets of size $q^2$, at each stage retaining only the sets which have the proper intersection with all already chosen.

This same method can be used without invoking the dual approach. Given an $(r,\lambda)$ design we could repeatedly delete points to get $(r,\lambda)$ designs with less points (although eventually they will be degenerate.) So the same process can be done in reverse: Returning to the $(4,2)$ case above, allow degenerate designs as a preliminary step. The empty design is technically OK. With one point there are 4 blocks: $1,1,1,1.$ Including a second point we need 4 blocks, exactly two of which were already there hence $12,12,1,1,2,2$ is the only possibility. With a third point we can split into 3 cases: The final design will have a triple of points in two common blocks (three is impossible) -or- there is a triple that are in one common block (but no triple in two) or that never happens. The next stage is then $123,123,1,1,2,2,3,3$ or $123,12,13,1,23,2,3$ or $12,12,13,13,23,23.$ We can continue but only so far, I think that going over 8 blocks would force singleton blocks from then on and keeping it to $8$ blocks or less forces $7$ points or less. For sufficiently larger $r=\lambda^2$ we would have to give up on being so systematic with all the possibilities but we could keep adding points by some process and backtrack if we get unacceptably spread out.

Answer 5

In the spirit of Yuichiro Fujuiwara's answer to my previous question, here's an approach that yields some examples: take a $(r,\lambda)$-design with $\lambda=1$ and a disjoint pair (aka a regular PBD $(v,K)$) and replicate the blocks $r$ times. I found a $(6,1)$-design in this paper by Lamken, Rees and Vanstone:

123 456 789 147 258 369

48 38 34 68 16 18

59 19 15 35 49 24

67 27 26 29 37 57

However, I'd love to see more examples of $(r,\lambda)$-designs with $r=\lambda^{2}$ that do not arise from this construction.