A t-(v,k,z) BIBD is a block design on v points with block size k such
that any two points are contained in exactly z blocks. A BIBD is
resolvable if the blocks can be partitioned such that each point is
contained in exactly one block in each partition. It is certain that
a 2-(28,7,2) BIBD exists. Can someone provide a resolvable 2-(28,7,2)
BIBD, or a proof that there is no such resolvable BIBD? |
Request for Question Clarification by
mathtalk-ga
on
26 Aug 2004 10:24 PDT
I believe the answer is negative, that no such design exists. Did you
have an application in mind for such a design?
regards, mathtalk-ga
|
Clarification of Question by
jamieas-ga
on
26 Aug 2004 11:18 PDT
The application is in parent-identifying codes. For some background
on IPP codes, see www.cs.technion.ac.il/users/eldar/cip.ps . The
design would give correspond directly to a 2-IPP code(actually a
2-traceability code) of length 9 over and alphabet of size 4 with 28
codewords, which can be modified to give more useful IPP codes.
I believe the answer to be negative as well. Otherwise, I would
imagine it would be easy to find a positive answer somewhere in the
literature. However, the lack of a definitive negative answer seems
puzzling. Hanani proved the existence of a 2-(28, 7, 2) BIBD, but I
can find nothing on whether a resolvable one can be constructed.
|
Clarification of Question by
jamieas-ga
on
26 Aug 2004 18:58 PDT
I should clarify that two blocks within any partition must not intersect.
|
Request for Question Clarification by
mathtalk-ga
on
26 Aug 2004 19:27 PDT
Such a design would require that any two blocks from different
parallel classes would always intersect in the same number of points.
With the given parameters, that number of points k^2/v is not an
integer, so there is no such design.
If you are interested in this negative result, I'll dress it up a bit and post it.
regards, mathtalk-ga
|
Clarification of Question by
jamieas-ga
on
27 Aug 2004 06:15 PDT
I had actually came across this last night. I found that designs such
as this, in which the number of blocks b=v+k-1 are strongly
resolvable, giving the intersection requirement you state. I would
definitely be interested in a simple proof of this fact though. The
only proofs I can find of b=v+k-1 implying strong resolution are quite
long and complex. If you have a simple proof of this (hopefully under
a page and using concepts from within design theory), I would
certainly be interested, and would pay the stated fee.
|
Request for Question Clarification by
mathtalk-ga
on
30 Aug 2004 18:15 PDT
Hi, jamieas-ga:
Perhaps your ideal proof of this result does not yet exist. The
definition of an affine resolvable design sprang from a 1942 paper:
A Note on the Resolvability of Balanced Incomplete Block Designs
by R. C. Bose in Sankhya 6 (p. 105-110), in which he first proved that
a resolvable (pairwise) BIBD with parameters (v,k,?) having b blocks
and r parallel classes must satisfy this improvement on Fisher's
inequality:
b ? v + r - 1
He further showed that equality in this comparison would imply that
two blocks from distinct parallel classes always intersect in kČ/v
points. Sometimes the equality b = v + r - 1 is taken as the defining
quality and sometimes the constant number of points where nondisjoint
blocks meet is taken as the definition of when a resolvable BIBD is
affine resolvable. But the difficult direction to prove is that the
equality implies constant size intersections, and that is the result
needed to answer your original question.
[Sankhya, The Indian Journal of Statistics: Contents, 1942]
(paper by Bose is about halfway down the page)
http://sankhya.isical.ac.in/pdfs/1942/42cont.html
The chain of results leading from the definition of balanced
incomplete block designs to Bose's sharpening of Fisher's inequality,
and finally to the result you have expressed interest in, is usually
established with the aid of linear algebra. In particular the
"incidence matrix" of the design plays a central role in the logical
development.
If you have examined several proofs of this type and found them
unsatisfactory, I do not believe my proof will be able to satisfy you
either. Reasoning from the definitions to the final theorem using
nothing more than the notions of linear algebra which one learns in a
sophomore level college course, I find the full explanation (including
proofs of Fisher's and Bose's inequalities) requires something on the
order of 300 lines. You can compare the detail of exposition I've
given to other theorem/proof type questions recently, but this
doubtless violates your "under a page" criterion (and possibly an
implied requirement to use only "concepts from within design theory").
Best wishes with your research on IPP codes, and thanks for posting
such an interesting Question!
regards, mathtalk-ga
|
