Pairwise balanced design
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 occurs in exactly
blocks of
. The integer
is the index of the pairwise balanced design. The notations
and
-PBD are often used when
.
Let be a
. A flat
in
is a pair
, where
and
, which has the property that
is also a pairwise balanced design. The order of the flat is
. In general, the degenerate pairwise balanced designs of orders
and
are considered to be flats of all pairwise balanced designs of order
. Such flats are trivial.
Let be a set of positive integers. Define
and
. Necessary conditions for the existence of a
are:
and
. R.M. Wilson [a5] has proved that these necessary conditions are asymptotically sufficient.
When there is a single block size (), 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
and
be sets of positive integers and let
be a positive integer. A group-divisible design of index
and order
(a
-GDD) is a triple
, where
is a finite set of cardinality
,
is a partition of
into parts (called groups) whose sizes lie in
, and
is a family of subsets (called blocks) of
which satisfy the properties:
a) If , then
.
b) Every pair of distinct elements of occurs in exactly
blocks or in one group, but not both.
c) . If
and if there are
groups of size
,
, then the
-GDD is of type
. This is exponential notation for the group type. A pairwise balanced design is a group-divisible design of group type
.
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 -GDD of type
; then
if for each ,
, there exists a
which contains a flat of order
, then there exists a
which contains flats of order
,
, and a flat of order
;
if for some there exists exactly one group of size
in the GDD (that is,
), and if for all
,
, there exists a
which contains a flat of order
, then there exists a
.
Wilson's fundamental construction [a4] states the following: Let be a GDD (the master GDD) with groups
. Suppose there exists a function
(a weight function) which has the property that for each block
there exists a
-GDD of type
(such a GDD is an "ingredient" GDD). Then there exists a
-GDD of type
![]() |
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 of positive integers is PBD-closed if the existence of a
implies that
belongs to
. Let
be a set of positive integers and let
. Then
is the PBD-closure of
. If
, the notation
is used. In this language, Wilson's asymptotic existence result states: The asymptotic sufficiency of the necessary conditions for the existence of
can be restated in terms of PBD-closed sets as follows. Let
be a PBD-closed set. Then
is eventually periodic with a period
(that is, there exists a constant
such that for every
,
). 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 be a PBD-closed set. Let
be a set of positive integers such that
. Then
is a generating set for
. An element
is essential in
if and only if
, that is, if and only if there does not exist a
. Let
denote the set of all essential elements in a PBD-closed set
. Then
is the unique minimal generating set (a basis) for
. Moreover,
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 |
Pairwise balanced design. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pairwise_balanced_design&oldid=52984