Skip to main content
1 of 3
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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,abde$ 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 don't know if every nontrivial (i.e. no single point blocks) $(4,2)$ design comes from this geometry but it shouldn't be too hard to figure out. 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.$

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. When $q$ is not a prime power we could still have some equations over the ring $\mathbb{Z}_q^3$ and we can always more or less randomly start generating sets of size $q^2$, at each stage retaining only the sets which have the proper intersection with all already chosen.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104