1
$\begingroup$

Give an example of BIBD(balanced Incomplete Block Design) with no repeated blocks in which λ > k.

Here which I need to find a BIBD where λ(each pair of vertices occurs together in exactly λ blocks) is greater than k(each block contains k vertices). For example, (v,b,r,1,2).

any suggestions?

  • 0
    I'm sure you can find a bunch of 2-sets such that each pair of elements appears in exactly one of the 2-sets. Have you tried?2012-04-18
  • 2
    Sorry, comment above was nonsense. But $\lambda=2$, $k=1$ can't possibly work - how can a pair of vertices appear in any blocks at all if each block has only one vertex? $\lambda=3$, $k=2$ can only be achieved if you allow multiple copies of some blocks. So I think you have to go to $\lambda=4$, $k=3$ to get any useful solution. See my answer.2012-04-19

1 Answers 1

2

Take a set of size 6, and let the blocks be the subsets of size 3. I think you'll find this works with $\lambda=4$, $k=3$.

  • 0
    then which means that v=6, r=3, k=3, λ=4.correct? then using the formula, r(k-1)=λ(v-1), 3(2)=4(5) which does not equal. Do I missing something?2012-04-19
  • 0
    $r$ is the number of blocks containing a given vertex, and in the example I have suggested, this is not 3. How many 3-subsets of a given 6-set contain a given element of the 6-set?2012-04-19
  • 0
    yeah, I guess that is my problem.... it's hard to picture them just by looking at the figures. It sometimes help me picturing of matrix where rows are the vertices and columns are the blocks, and sum of each rows give us the r-regular and sum of columns gives us k-uniform, is it correct and can I apply this picturing in this problem?2012-04-19
  • 0
    so there will be 6 choose 3 many different blocks, along with vertices 1 through 6, correct?2012-04-19
  • 0
    Yes, the number of blocks is the number of 3-subsets of a 6-set, which is 6-choose-3. I'm not sure I understand your matrix, but if what you are saying is one row for each vertex and one column for each block, and a 1 in position ij if vertex i is in block j, and a 0 in position ij otherwise, then the sum of the columns gives you $r$, the sum of the rows gives $k$, and you can use this to picture the problem.2012-04-19
  • 0
    Thanks, so, so far I have got, b=40, v=6, k=3, λ=4 but how do I get the r?2012-04-19
  • 0
    Using the two formula for BIBD, such that bk=rv and r(k-1)=λ(v-1), I get different value for r, which result of our design is not BIBD?2012-04-19
  • 0
    $b$ is the number of blocks, which is the number of 3-subsets of a 6-set, which is *not* 40. $r$ is the number of 3-element subsets of abcdef containing f.2012-04-19