Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that a balanced, uniform incomplete design is regular.

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

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


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.