Prove that a balanced, uniform incomplete design is regular.
For this question, I have no clue where to start, any suggestions?
Prove that a balanced, uniform incomplete design is regular.
For this question, I have no clue where to start, any suggestions?
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.