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}(\vu,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 , then .

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