Pairwise balanced design

$$ \newcommand{\PBD}{\operatorname{PBD}} $$

PBD

Let $K$ be a set of positive integers and let $\lambda$ be a positive integer. A pairwise balanced design ($\operatorname{PBD}(\nu,K,\lambda)$ or $(K,\lambda)$-PBD) of order $\nu$ with block sizes from $K$ is a pair $(V,\mathcal{B})$ where $V$ is a finite set (the point set) of cardinality $\nu$ and $\mathcal{B}$ is a family of subsets (blocks) of $V$ which satisfy the properties:

1) If $B\in\mathcal{B}$, then $|B|\in K$.

2) Every pair of distinct elements of $V$ occurs in exactly $\lambda$ blocks of $\mathcal{B}$. The integer $\lambda$ is the index of the pairwise balanced design. The notations $\PBD(v,K)$ and $K$-PBD are often used when $\lambda=1$.

Let $D = (V,\mathcal{B})$ be a $\PBD(v,K)$. A flat $\mathcal{F}$ in $D$ is a pair $(F,\mathcal{C})$, where $F \subset V$, and $(\mathcal{C} \subset \mathcal{B})$, which has the property that $(F, \mathcal{C})$ is also a pairwise balanced design. The order of the flat is $|F|$. In general, the degenerate pairwise balanced designs of orders $0$ and $1$ are considered to be flats of all pairwise balanced designs of order $v > 1$. Such flats are trivial.

Let $K$ be a set of positive integers. Define $\alpha(K) = \gcd\{k-1: k \in K\}$ and $\beta(K) = \gcd \{k(k-1) : k \in K\}$. Necessary conditions for the existence of a $\PBD(v,K)$ are: $v-1 \equiv 0 \pmod{\alpha(K)}$ and $v(v-1) \equiv 0 \pmod{\beta(K)}$. R.M. Wilson [a5] has proved that these necessary conditions are asymptotically sufficient.

When there is a single block size ($K = \{k\}$), a pairwise balanced design is a balanced incomplete block design (a BIBD, see Block design). Variants of pairwise balanced designs arise in which there are holes, i.e. subsets of the point set on which the pairs do not appear in blocks. The most important arise when the union of the holes is the entire point set. Let $K$ and $G$ be sets of positive integers and let $\lambda$ be a positive integer. A group-divisible design of index $\lambda$ and order $v$ (a $(K,\lambda)$-GDD) is a triple $(V,\mathcal{G}, \mathcal{B})$, where $V$ is a finite set of cardinality $v$, $\mathcal{G}$ is a partition of $V$ into parts (called groups) whose sizes lie in $G$, and $\mathcal{B}$ is a family of subsets (called blocks) of $V$ which satisfy the properties:

a) If $B \in \mathcal{B}$, then $|B| \in K$.

b) Every pair of distinct elements of $V$ occurs in exactly $\lambda$ blocks or in one group, but not both.

c) $|\mathcal{G}| > 1$. If $v = a_1 g_1 + \dots a_s g_s$ and if there are $a_i$ groups of size $g_i$, $i = 1, \ldots, s$, then the $(K,\lambda)$-GDD is of type $g_1^{a_1} \dots g_s^{a_s}$. This is exponential notation for the group type. A pairwise balanced design is a group-divisible design of group type $1^v$.

Group-divisible designs are extensively employed in the construction of pairwise balanced designs. A basic example is the singular direct product [a7]: Suppose that there exists a $K$-GDD of type $g_1^{a_1} \dots g_s^{a_s}$; then

if for each $g_i$, $i=1,\ldots,s$, there exists a $\PBD(g_i +f, K)$ which contains a flat of order $f$, then there exists a $\PBD((\sum_{i=1}^s a_ig_i) + f, K)$ which contains flats of order $g_i+f$, $i=1,\ldots,s$, and a flat of order $f$;

if for some $j$ there exists exactly one group of size $g_j$ in the GDD (that is, $a_j = 1$), and if for all $i=1,\ldots,s$, $i\ne j$, there exists a $\PBD(g_i + f, K)$ which contains a flat of order $f$, then there exists a $\PBD\left( (\sum_{i=1}^s a_ig_i) + f, K\cup \{g_j+f\}\right)$.

Wilson's fundamental construction [a4] states the following: Let $(V, \mathcal{G}, \mathcal{B})$ be a GDD (the master GDD) with groups $G_1, \ldots, G_t$. Suppose there exists a function $w : V \to \Z^+ \cup \{0\}$ (a weight function) which has the property that for each block $B = \{x_1, \ldots, x_k\} \in \mathcal{B}$ there exists a $K$-GDD of type $[w(x_1), \ldots, w(x_k)]$ (such a GDD is an "ingredient" GDD). Then there exists a $K$-GDD of type

$$ \left[ \sum_{x\in G_1} w(x) , \ldots, \sum_{x\in G_t} w(x)\right]. $$

The block sizes of the master GDD do not necessarily occur among the block sizes of the constructed GDD. Most recursive constructions for pairwise balanced designs employ some application or variant of Wilson's fundamental construction; see [a1], [a2], [a6], [a7].

In addition to recursive methods, numerous pairwise balanced designs have been constructed directly using computational methods, and by combinatorial operations on other designs, notably projective planes and transversal designs [a6], [a7]. However, the greatest significance of pairwise balanced designs is in their application to the solution of existence questions for other types of designs. The generic approach here is as follows:

A set $S$ of positive integers is PBD-closed if the existence of a $\PBD(v, S)$ implies that $v$ belongs to $S$. Let $K$ be a set of positive integers and let $B(K) = \{v : \exists \PBD(v, K)\}$. Then $B(K)$ is the PBD-closure of $K$. If $K = \{k\}$, the notation $B(k)$ is used. In this language, Wilson's asymptotic existence result states: The asymptotic sufficiency of the necessary conditions for the existence of $\PBD(v, K)$ can be restated in terms of PBD-closed sets as follows. Let $K$ be a PBD-closed set. Then $K$ is eventually periodic with a period $\beta(K)$ (that is, there exists a constant $C(K)$ such that for every $k \in K$, $\{v : v \ge C(K), v \equiv k \pmod{\beta(K)}\} \subseteq K$). This makes the theory of PBD-closure useful.

A few examples of a certain set of objects can prove sufficient to establish the existence of an entire set of objects.

Let $K$ be a PBD-closed set. Let $G$ be a set of positive integers such that $K = B(G)$. Then $G$ is a generating set for $K$. An element $x \in K$ is essential in $K$ if and only if $x \notin B(K\setminus \{x\})$, that is, if and only if there does not exist a $\PBD(x, K\setminus\{x\})$. Let $E_K$ denote the set of all essential elements in a PBD-closed set $K$. Then $E_K$ is the unique minimal generating set (a basis) for $K$. Moreover, $E_K$ is finite.

Using the notion of PBD-closed sets, combinatorial existence questions often reduce to two simpler steps: establishing that the set of interest is PBD-closed, and then establishing existence for each element (order of a PBD) in the basis of the PBD-closed set. These two simpler steps suffice to establish existence for all admissible orders. For this reason, substantial effort has been invested in determining generating sets and bases for PBD-closed sets; see [a8].

References

[a1]	T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986) Zbl 602.05001
[a2]	C.J. Colbourn, A. Rosa, "Triple systems" , Oxford Univ. Press (1999)
[a3]	H. Hanani, "Balanced incomplete block designs and related designs" Discrete Math. , 11 (1975) pp. 255–369
[a4]	R.M. Wilson, "An existence theory for pairwise balanced designs I: Composition theorems and morphisms" J. Combin. Th. A , 13 (1971) pp. 220–245
[a5]	R.M. Wilson, "An existence theory for pairwise balanced designs II: The structure of PBD-closed sets and the existence conjectures" J. Combin. Th. A , 13 (1971) pp. 246–273
[a6]	R.C. Mullin, H-D.O.F. Gronau, "PBDs and GDDs: The basics" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , CRC Handbook of Combinatorial Designs , CRC (1996) pp. 185–192
[a7]	R.C. Mullin, H.-D.O.F. Gronau, "PBDs: Recursive constructions" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , CRC Handbook of Combinatorial Designs , CRC (1996) pp. 193–203
[a8]	F. Bennett, H.D.O.F. Gronau, A.C.H. Ling, R.C. Mullin, "PBD-closure" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , CRC Handbook of Combinatorial Designs , CRC (1996) pp. 203–213