# BIBD- block design question combinatorics

Prove that a balanced, uniform incomplete design is regular.

For this question, I have no clue where to start, any suggestions?

-
Start with the definitions. What's a balanced incomplete block design? What does "uniform" mean? What does "regular" mean? –  Gerry Myerson Apr 18 '12 at 4:18
it's regular if each vertex exactly occurs in r blocks, and it's uniform if each block contains k-vertices. so which means if each block contains k-vertices then it is regular? –  user28699 Apr 18 '12 at 4:21
I cannot parse this question. For me a block design or, better $(v,b,r,k, \lambda)$ design comes with regularness. So, I would like to see your definitions for the terms here. Please consider adding the definitions. –  user21436 Apr 18 '12 at 5:01
By definition, if in a k-uniform, regular incomplete design, each pair of vertices occurs together in exactly λ blocks then we say that (S,B) is Balanced incomplete Block with parameter (v,b,r,k,λ). –  user28699 Apr 18 '12 at 5:11
I think what Kannappan is asking is, what would a non-regular BIBD look like? Doesn't your definition of BIBD already imply regularity? –  Gerry Myerson Apr 18 '12 at 6:48

A pairwise balanced design (or PBD) is a set X together with a family of subsets of X (which need not have the same size and may contain repeats) such that every pair of distinct elements of X is contained in exactly λ (a positive integer) subsets.

A PBD is said to be uniform if each block has the same size, typically denoted k. A PBD is said to be regular if each element belongs to the same number of blocks.

We want to show:

Lemma: A uniform PBD is regular.

Proof: Take a uniform PBD; so each block has size k. Pick an element, x say.

Construct a bipartite multigraph: on the left are the pairs (x,w), for all w (except x), and on the right are the blocks B containing x. We draw an edge from (x,w) to B if w ∈ B too.

Each vertex on the left has degree λ. And there are v-1 elements other than x (here v=|X|). Hence the number of edges in the graph is (v-1)λ.

Each vertex on the right has degree k-1. Let's suppose there are r vertices on the right. Hence the number of edges in the graph is r(k-1).

Hence (v-1)λ=r(k-1), and r is determined from v,k,λ (and is independent of the choice of x). Hence our PBD is regular.

-