Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Simple BIBD are defined as those designs in which incindence relation is "is element". So effectively blocks are subsets of points. Equivalently there should be no "repeating blocks" ie. blocks that aren't uniquely determined by its 'elements' (here 'elements' means in sense of incidence relation).

For fixed block $B_0$ (Block-)residual designs (of symmetric $(v,k,\lambda)$-design $(\mathcal{P},\mathcal{B},\mathcal{I})$=(points,blocks,relation)) is defined as incidence structure with points $\mathcal{P}\setminus B_0$ and blocks $ \{ B \setminus B_0 : B\in \mathcal{B}, B\neq B_0 \} $ and incidence inherited from initial design.

This residual design is allowed to have repeted blocks (ie. not to be simple). In that case parameters of derived design are $(v-k,k-\lambda,\lambda)$.

But from a few simple examples it seems that if there are any repeated blocks, than there is fixed $f$ such that every block is repeated exactly $f$ times. So we can simply exclude those repated blocks and get SIMPLE $(v-k,k-\lambda,\frac{\lambda}{f})$ design.

Is this true? If not what is counter-example? If it is in fact true, how to prove it?

Additionaly we suppose that $k-\lambda\geq 2$.


EDIT (clarification): Maybe I wasn't clear enough. Bottom line is that if you start with SIMPLE SYMMETRIC BIBD $(\mathcal{P},\mathcal{B},\in)$ with $k-\lambda \geq 2$ is it true that "residual design" $(\mathcal{P}\setminus B_0,\{ B \setminus B_0 : B\in \mathcal{B}, B\neq B_0 \},\in)$ is DESIGN AT ALL?! (Note that here same blocks merge into one block since relation is '$\in$'). It will be if it is true that there is fixed $f$ such that every block is repeated exactly $f$ times if we interpret $\{ B \setminus B_0 : B\in \mathcal{B}, B\neq B_0 \}$ as multiset.

It isn't hard to prove that if $\lambda=1$ (since we have $k−\lambda\geq 2$) this is true and there aren't repeated blocks ie. $f=1$.

But what about $\lambda >1$?

share|improve this question
1  
There are many counterexamples. As Cameron and van Lint explain in the beginning of their text Designs, Graphs, Codes and Their Links, if $\lambda < k < v-\lambda$ then a $(v,k,\lambda)$ design with repeated blocks is tantamount to a positive solution of a linear system with more variables than equations, and thus always exists, unlike BIBD's without repeats for which $v,k,\lambda$ must satisfy many constraints. –  Noam D. Elkies Mar 12 '12 at 0:32
    
Simple counterexample: $(v,k,\lambda) = (5,1,2)$, $$ {\cal B} = \lbrace \lbrace1,2\rbrace, \lbrace2,3\rbrace, \lbrace3,1\rbrace, \lbrace4,5\rbrace, \lbrace4,5\rbrace \rbrace. $$ –  Noam D. Elkies Mar 12 '12 at 0:46
    
@Noam: I don't see how this answers my question :( I gave clarification above. –  Mate Mar 12 '12 at 7:28
    
Sorry, indeed it seemed to me that you were asking whether any design that already has repeated blocks must have constant multiplicity. For your actual intended question I might have to think some more... –  Noam D. Elkies Mar 13 '12 at 1:32
add comment

1 Answer

up vote 2 down vote accepted

A necessary condition for residual designs not being simple is $k\le 2\lambda$. If $k>2\lambda$, repeated blocks in the residual design would correspond to blocks of the symmetric design intersecting in more than $\lambda$ points, which is not possible.

For $k\le 2\lambda$ repeated blocks are indeed possible, and the residual design need not be the multiple of a simple design. The smallest example I could come up with is a (15,8,4) design with the following incidence matrix:

111100011110000
111100000001111
110011011001100
110011000110011
101010111000011
101010100111100
100101110101010
100101101010101
011001110100101
011001101011010
010110110011001
010110101100110
001111010010110
001111001101001
000000011111111

The residual with respect to the block corresponding to the first column of the matrix is a non-simple (7,4,4) design. Three of its blocks have multiplicity 2, and the remaining blocks are not repeated.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.