Combinatorial Designs - Key Properties

Combinatorial designs satisfy necessary numerical conditions that constrain their parameters. Understanding these relationships guides construction and determines existence.

DefinitionFisher's Inequality

In a $2$ - $(v, k, \lambda)$ design with $v > k$ , the number of blocks satisfies $b \geq v$ . Equality holds if and only if the design is symmetric (every pair of blocks intersects in $\lambda$ points).

DefinitionParameter Relations for BIBD

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

Counting equation: $bk = vr$ where $r$ is the replication number (number of blocks containing any given point).

Balanced equation: $\lambda(v-1) = r(k-1)$

These follow from double-counting: the first counts point-block incidences, the second counts pairs within blocks containing a fixed point.

From these relations: $r = \frac{\lambda(v-1)}{k-1}$ and $b = \frac{vr}{k} = \frac{\lambda v(v-1)}{k(k-1)}$ .

For integer solutions, necessary conditions include:

$k-1$ divides $\lambda(v-1)$
$k$ divides $\lambda v(v-1)$

These are necessary but not always sufficient for existence.

ExampleParameter Calculation

For a $2$ - $(15, 3, 1)$ design:

$r = \frac{1(15-1)}{3-1} = \frac{14}{2} = 7$ (each point in 7 blocks)
$b = \frac{1 \cdot 15 \cdot 14}{3 \cdot 2} = \frac{210}{6} = 35$ blocks

This design exists (Steiner triple system of order 15).

DefinitionResolvability

A design is resolvable if its blocks can be partitioned into resolution classes, where each class partitions $V$ (every point appears exactly once in each class).

Example: Round-robin tournament with $v$ teams and $k=2$ (matches) is resolvable when $v$ is even.

DefinitionAutomorphism Group

An automorphism of a design $(V, \mathcal{B})$ is a permutation $\sigma$ of $V$ that preserves blocks: $B \in \mathcal{B}$ iff $\sigma(B) \in \mathcal{B}$ .

The automorphism group captures the design's symmetries. Some designs (like the Fano plane) have large automorphism groups (order 168 for Fano), while others are asymmetric.

Remark

The Bruck-Ryser-Chowla theorem provides stronger necessary conditions: For a symmetric $2$ - $(v,k,\lambda)$ design, if $v$ is even, then $k - \lambda$ must be a perfect square. If $v$ is odd, the Diophantine equation $x^2 = (k-\lambda)y^2 + (-1)^{(v-1)/2}\lambda z^2$ must have a non-trivial integer solution. These number-theoretic obstructions explain why certain parameter sets have no designs (e.g., no $2$ - $(22,8,4)$ design exists). Wilson's theorem provides sufficient conditions for large $v$ , showing most admissible parameters do yield designs when $v$ is large enough.

These properties constrain design existence and guide systematic construction methods.