Skip to main content
added 1283 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

So for $(r,\lambda)=(4,2)$ we just need some $4$-sets, each pair having intersection of size $2$. The simple example $abcd,abde$$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.)

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.

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.)

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.

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.)

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.

added 313 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I don't know ifthink that 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, 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. WhenI 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$ and$\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 generatingselecting sets of size $q^2$, at each stage retaining only the sets which have the proper intersection with all already chosen.

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.

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.

Source Link
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.