On the PBD-closure of sets containing 3 (Q1302161)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the PBD-closure of sets containing 3 |
scientific article |
Statements
On the PBD-closure of sets containing 3 (English)
0 references
20 December 1999
0 references
A partial pairwise balanced design \(\text{PPBD}[v,K']\) with block set \(\mathcal F\) is called a \((K',K)\)-completable prestructure of order \(v\) if there exists a \(\text{PBD}[v,K]\) on the same point set and with block set \(\mathcal B\), where \(\mathcal F \subseteq \mathcal B\), \(\mathcal K' \subseteq \mathcal K\) and if \(B \in \mathcal B \setminus \mathcal F\), then \(|B|\in K \setminus K'\). Obviously nonexistence of a \((K',K)\)-completable prestructure of order \(v\) implies nonexistence of a \(\text{PBD}[v,K]\). \textit{E. Mendelsohn} and \textit{R. Rees} [Mandatory representation designs, J. Comb. Theory, Ser. A 49, No. 2, 349-362 (1988; Zbl 0661.05014)] used the idea to establish necessary conditions for the existence of \(\text{PBD}[v,\{3,k\}]\)s with at least one block of size \(k\). Also \textit{H.-D. O. F. Gronau, R. C. Mullin} and \textit{C. Pietsch} [The closure of all subsets of \(\{3,4,\dots,10\}\) which include 3, Ars Comb. 41, 129-161 (1995; Zbl 0844.05018)] determined the complete closure of all subsets of the set \(\{3,4,\dots,10\}\) which contain the number 3. In this paper the author generalizes the proofs of Gronau et al. in order to determine the exact closure of all subsets \(K\) of the set \(\{3,4,\dots,22\}\) with \(K \cap \{11,12,\dots,22\} \neq \varnothing\) and \(3 \in K\). A range of necessary conditions for the existence of a prestructure is very useful in ruling out the existence of many PBDs. In addition the author uses a variety of recursive constructions and existence results from \textit{C. J. Colbourn} and \textit{J. H. Dinitz} [The CRC handbook of combinatorial designs, CRC Press, Boca Raton (1996; Zbl 0836.00010)]. To start the recursive constructions small order ``ingredient'' PBDs are produced using hill climbing, a good method for constructing designs with block length 3. The paper concludes with an appendix providing statistics on the usage of theorems and lemmas in determining the nonexistence of PBDs, along with a table of the closure of all subsets \(K \subset \{3,4,\dots,22\}\) with \(3 \in K\), \(K \cap \{11,12,\dots,22\}\neq \varnothing\) with the cardinality of \(K\) at most \(3\). A complete table of results is located at ftp://ftp.math.uni-rostock.de/pub/members/mguttm/closure.htm.
0 references
pairwise balanced design
0 references
PBD-closure
0 references