Combinatorial Designs - Key Proof

The fundamental parameter relations for balanced designs follow from double-counting arguments, illustrating the power of combinatorial reasoning.

DefinitionBIBD Parameter Relations

For a $2$ - $(v,k,\lambda)$ design with $b$ blocks and replication number $r$ :

Counting relation: $bk = vr$
Balance relation: $\lambda(v-1) = r(k-1)$

Proof of Counting Relation:

We count the number of point-block incidences (pairs $(p,B)$ where point $p$ is in block $B$ ) in two ways.

Method 1 (counting by blocks): Each block contains exactly $k$ points. With $b$ blocks total: $\text{Incidences} = bk$

Method 2 (counting by points): Each point appears in exactly $r$ blocks (by definition of replication number). With $v$ points total: $\text{Incidences} = vr$

Since both count the same thing: $bk = vr$ . $\square$

Proof of Balance Relation:

We count pairs $(p,q,B)$ where points $p$ and $q$ (with $p \neq q$ ) both appear in block $B$ .

Method 1 (counting by point pairs): Fix a point $p$ . There are $v-1$ choices for the other point $q \neq p$ . The pair $\{p,q\}$ appears in exactly $\lambda$ blocks (by the $2$ -design property).

Total for all $v$ choices of $p$ : $\text{Count} = v(v-1)\lambda$

But this counts each triple $(p,q,B)$ twice: once with $p$ as the "fixed" point and once with $q$ as the fixed point. Therefore: $\text{Triples} = \frac{v(v-1)\lambda}{2}$

Method 2 (counting by blocks): Fix a block $B$ containing $k$ points. The number of unordered pairs from these $k$ points is $\binom{k}{2} = \frac{k(k-1)}{2}$ .

With $b$ blocks total: $\text{Triples} = b \cdot \frac{k(k-1)}{2}$

Equating the two counts: $\frac{v(v-1)\lambda}{2} = b \cdot \frac{k(k-1)}{2}$ $v(v-1)\lambda = bk(k-1)$

Substituting $bk = vr$ from the counting relation: $v(v-1)\lambda = vr(k-1)$ $\lambda(v-1) = r(k-1)$

This completes the proof. $\square$

Alternative Proof (for Balance Relation):

Fix a point $p$ . It appears in $r$ blocks. Each of these blocks contains $k-1$ other points (besides $p$ ).

Total number of point pairs $(p,q)$ with $p$ in a block is $r(k-1)$ (counting with multiplicity).

But there are $v-1$ other points $q \neq p$ , and each pair $\{p,q\}$ appears in exactly $\lambda$ blocks.

Therefore: $(v-1) \cdot \lambda = r(k-1)$ . $\square$

ExampleVerification for Fano Plane

For the $2$ - $(7,3,1)$ Fano plane:

From balance relation: $r = \frac{\lambda(v-1)}{k-1} = \frac{1 \cdot 6}{2} = 3$ ✓
From counting relation: $b = \frac{vr}{k} = \frac{7 \cdot 3}{3} = 7$ ✓

Each point is in 3 lines, there are 7 lines total, and each line has 3 points.

Remark

These relations, though simple, are fundamental constraints on design parameters. They immediately eliminate many impossible parameter sets (e.g., if $k-1$ doesn't divide $\lambda(v-1)$ , no design exists). Combined with Fisher's inequality and number-theoretic constraints (Bruck-Ryser-Chowla theorem), they significantly restrict the possible parameter values. The relations also guide design construction: given $v$ , $k$ , $\lambda$ satisfying necessary conditions, we can compute the required $b$ and $r$ , then attempt construction. These double-counting arguments exemplify the combinatorial method: count the same objects in different ways to derive identities.