View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003012.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003013.png" />.

2) Every pair of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003014.png" /> occurs in exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003015.png" /> blocks of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003016.png" />. The integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003017.png" /> is the index of the pairwise balanced design. The notations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003019.png" />-PBD are often used when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003020.png" />.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003021.png" /> be a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003022.png" />. A flat <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003023.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003024.png" /> is a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003025.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003027.png" />, which has the property that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003028.png" /> is also a pairwise balanced design. The order of the flat is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003029.png" />. In general, the degenerate pairwise balanced designs of orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003031.png" /> are considered to be flats of all pairwise balanced designs of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003032.png" />. Such flats are trivial.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003033.png" /> be a set of positive integers. Define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003035.png" />. Necessary conditions for the existence of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003036.png" /> are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003038.png" />. R.M. Wilson [[#References|[a5]]] has proved that these necessary conditions are asymptotically sufficient.

When there is a single block size (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003039.png" />), a pairwise balanced design is a balanced incomplete block design (a BIBD, see [[Block design|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003041.png" /> be sets of positive integers and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003042.png" /> be a positive integer. A group-divisible design of index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003043.png" /> and order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003044.png" /> (a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003045.png" />-GDD) is a triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003046.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003047.png" /> is a finite set of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003049.png" /> is a partition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003050.png" /> into parts (called groups) whose sizes lie in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003051.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003052.png" /> is a family of subsets (called blocks) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003053.png" /> which satisfy the properties:

a) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003054.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003055.png" />.

b) Every pair of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003056.png" /> occurs in exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003057.png" /> blocks or in one group, but not both.

c) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003058.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003059.png" /> and if there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003060.png" /> groups of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003062.png" />, then the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003063.png" />-GDD is of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003064.png" />. This is exponential notation for the group type. A pairwise balanced design is a group-divisible design of group type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003065.png" />.

Group-divisible designs are extensively employed in the construction of pairwise balanced designs. A basic example is the singular direct product [[#References|[a7]]]: Suppose that there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003066.png" />-GDD of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003067.png" />; then

if for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003069.png" />, there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003070.png" /> which contains a flat of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003071.png" />, then there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003072.png" /> which contains flats of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003074.png" />, and a flat of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003075.png" />;

if for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003076.png" /> there exists exactly one group of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003077.png" /> in the GDD (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003078.png" />), and if for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003079.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003080.png" />, there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003081.png" /> which contains a flat of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003082.png" />, then there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003083.png" />.

Wilson's fundamental construction [[#References|[a4]]] states the following: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003084.png" /> be a GDD (the master GDD) with groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003085.png" />. Suppose there exists a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003086.png" /> (a weight function) which has the property that for each block <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003087.png" /> there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003088.png" />-GDD of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003089.png" /> (such a GDD is an  "ingredient"  GDD). Then there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003090.png" />-GDD of type

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003091.png" /></td> </tr></table>

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 [[#References|[a1]]], [[#References|[a2]]], [[#References|[a6]]], [[#References|[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 [[#References|[a6]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003092.png" /> of positive integers is PBD-closed if the existence of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003093.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003094.png" /> belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003095.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003096.png" /> be a set of positive integers and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003097.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003098.png" /> is the PBD-closure of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p12003099.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030100.png" />, the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030101.png" /> is used. In this language, Wilson's asymptotic existence result states: The asymptotic sufficiency of the necessary conditions for the existence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030102.png" /> can be restated in terms of PBD-closed sets as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030103.png" /> be a PBD-closed set. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030104.png" /> is eventually periodic with a period <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030105.png" /> (that is, there exists a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030106.png" /> such that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030108.png" />). 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030109.png" /> be a PBD-closed set. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030110.png" /> be a set of positive integers such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030111.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030112.png" /> is a generating set for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030113.png" />. An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030114.png" /> is essential in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030115.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030116.png" />, that is, if and only if there does not exist a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030117.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030118.png" /> denote the set of all essential elements in a PBD-closed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030119.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030120.png" /> is the unique minimal generating set (a basis) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030121.png" />. Moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p120/p120030/p120030122.png" /> 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 [[#References|[a8]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Beth,   D. Jungnickel,   H. Lenz,   "Design theory" , Cambridge Univ. Press  (1986) {{ZBL|602.05001}}</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  C.J. Colbourn,   A. Rosa,   "Triple systems" , Oxford Univ. Press  (1999)</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Hanani,   "Balanced incomplete block designs and related designs"  ''Discrete Math.'' , '''11'''  (1975)  pp. 255–369</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  R.M. Wilson,   "An existence theory for pairwise balanced designs I: Composition theorems and morphisms"  ''J. Combin. Th. A'' , '''13'''  (1971)  pp. 220–245</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  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</TD></TR>
<TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR>
</table>