×

zbMATH — the first resource for mathematics

The asymptotic existence of resolvable group divisible designs. (English) Zbl 1262.05016
Summary: A group divisible design (GDD) is a triple \((X,\mathcal{G},\mathcal{B})\) which satisfies the following properties:
(1)
\({\mathcal G}\) is a partition of \(X\) into subsets called groups;
(2)
\({\mathcal B}\) is a collection of subsets of \(X\), called blocks, such that a group and a block contain at most one element in common; and
(3)
every pair of elements from distinct groups occurs in a constant number \(\lambda\) blocks.
This parameter \(\lambda\) is usually called the index. A \(k\)-GDD of type \(g^u\) is a GDD with block size \(k\), index \(\lambda= 1\), and \(u\) groups of size \(g\). A GDD is resolvable if the blocks can be partitioned into classes such that each point occurs in precisely one block of each class. We denote such a design as an RGDD. For fixed integers \(g\geq 1\) and \(k\geq 2\), we show that the necessary conditions for the existence of a \(k\)-RGDD of type \(g^u\) are sufficient for all \(u\geq u_0(g, k)\).
As a corollary of this result and the existence of large resolvable graph decompositions, we establish the asymptotic existence of resolvable graph GDDs, \(G\)-RGDDs, whenever the necessary conditions for the existence of \((v,G,1)\)-RGDs are met. We also show that, with a few easy modifications, the techniques extend to general index.

MSC:
05B30 Other designs, configurations
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chan, Asymptotic existence results on specific graph decompositions (2010)
[2] Chang, An existence theory for group divisible designs (1976)
[3] Y. M. Chee C. J. Colbourn A. C. H. Ling R. M. Wilson Covering and packing for pairs · Zbl 1314.05025
[4] The CRC Handbook of Combinatorial Designs (2006)
[5] Danziger, Class-uniformly resolvable group divisible structures I: resolvable group divisible designs, Elec J Combin 11 (2004) · Zbl 1053.05013
[6] Dukes, Asymptotic existence of resolvable graph designs, Canad Math Bull 50 pp 504– (2007) · Zbl 1152.05015 · doi:10.4153/CMB-2007-050-x
[7] Dukes, An existence theory for loopy graph decompositions, J Combin Des 19 pp 280– (2011) · Zbl 1223.05227 · doi:10.1002/jcd.20280
[8] Furino, Frames and Resolvable Designs (1996)
[9] Lamken, Decompositions of edge-colored complete graphs, J Combin Theory Ser A 89 pp 149– (2000) · Zbl 0937.05064 · doi:10.1006/jcta.1999.3005
[10] Liu, Asymptotic existence theorems for frames and group divisible designs, J Combin Theory Ser A 114 pp 410– (2007) · Zbl 1115.05008 · doi:10.1016/j.jcta.2006.06.006
[11] Lu, An existence theory for resolvable balanced incomplete block designs (Chinese), Acta Math Sinica 27 pp 458– (1984)
[12] Mohácsy, The asymptotic existence of group divisible designs of large order with index one, J Combin Theory Ser A 118 pp 1915– (2011) · Zbl 1236.05052 · doi:10.1016/j.jcta.2011.04.003
[13] Ray-Chaudhuri, A Survey of combinatorial theory pp 361– (1973) · doi:10.1016/B978-0-7204-2262-7.50035-1
[14] Rees, On combinatorial designs with subdesigns, Discrete Math 77 pp 259– (1989) · Zbl 0694.05010 · doi:10.1016/0012-365X(89)90365-8
[15] Rees, Frames with block size four, Can J Math 44 (5) pp 1030– (1992) · Zbl 0769.05020 · doi:10.4153/CJM-1992-063-x
[16] Vanstone, Doubly resolvable designs, Discrete Math 29 pp 77– (1980) · Zbl 0447.05010 · doi:10.1016/0012-365X(90)90288-S
[17] Wilson, An existence theory for pairwise balanced designs II: The structure of PBD-closed sets and the existence conjectures, J Combin Theory Ser A 13 pp 246– (1972) · Zbl 0263.05015 · doi:10.1016/0097-3165(72)90029-5
[18] Wilson, An existence theory for pairwise balanced designs III: Proof of the existence conjectures, J Combin Theory Ser A 18 pp 71– (1975) · Zbl 0295.05002 · doi:10.1016/0097-3165(75)90067-9
[19] Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congr Numer XV pp 647– (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.