prob028: balanced incomplete block designs

proposed by Steven Prestwich
s.prestwich@cs.ucc.ie

Results

It can be proved that for a BIBD to exist its parameters must satisfy the conditions rv=bk, lambda(v-1)=r(k-1) and b >= v, but these are not sufficient conditions. Constructive methods can be used to design BIBDs of special forms but BIBD generation is challenging as a CSP. One source of intractability is the large number of symmetries: given any solution, any two rows or columns may be exchanged to obtain another solution. The number of solutions ranges from 0 to over 10^200. Most interestingly, there are several instances whose status (solvable or unsolvable) is currently unknown. Here are the open problems (with vb <= 10000) listed by Colbourn and Dinitz:

v b r k lambda
46 69 9 6 1
51 85 10 6 1
61 122 12 6 1
22 33 12 8 4
40 52 13 10 3
46 69 15 10 3
65 80 16 13 3
81 81 16 16 3
49 98 18 9 3
55 99 18 10 3
85 102 18 15 3
39 57 19 13 6
61 122 20 10 3
46 92 20 10 4
45 75 20 12 5
57 76 20 15 5
57 133 21 9 3
40 60 21 14 7
85 105 21 17 4
45 90 22 11 5
45 66 22 15 7
55 132 24 10 4
69 92 24 18 6
51 85 25 15 7
51 75 25 17 8
55 135 27 11 5
55 99 27 15 7
57 84 28 19 9
57 76 28 21 10
85 85 28 28 9
34 85 30 12 10
58 87 30 20 10
56 88 33 21 12
78 117 33 22 9
64 96 33 22 11
97 97 33 33 11
69 102 34 23 11
46 161 35 10 7
51 85 35 21 14
64 80 35 28 15
69 138 36 18 9
52 104 36 18 12
49 84 36 21 15
55 90 36 22 14
70 105 36 24 12
85 85 36 36 15
75 111 37 25 12
58 116 38 19 12
76 114 39 26 13
66 99 39 26 15
57 152 40 15 10
65 104 40 25 15