1
$\begingroup$

Prove that a balanced, uniform incomplete design is regular.

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

  • 1
    I think what Kannappan is asking is, what would a non-regular BIBD look like? Doesn't your definition of BIBD already imply regularity?2012-04-18

1 Answers 1

2

This question is likely asking about pairwise balanced designs.

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.