An Existence Theory for Incomplete Designs

Dukes, Peter ; Lamken, Esther R. ; Ling, Alan C. H.

Canadian mathematical bulletin, Tome 59 (2016) no. 2, pp. 287-302

Résumé

An incomplete pairwise balanced design is equivalent to a pairwise balanced design with a distinguished block, viewed as a ‘hole’. If there are v points, a hole of size $w$ , and all (other) block sizes equal $k$ , this is denoted $\text{IPBD}\left( \left( v;w \right),\,k \right)$ . In addition to congruence restrictions on $v$ and $w$ , there is also a necessary inequality: $v\,>\,\left( k\,-\,1 \right)w$ . This article establishes two main existence results for $\text{IPBD}\left( \left( v;w \right),\,k \right)$ : one in which $w$ is fixed and $v$ is large, and the other in the case $v>\,\left( k-1+\varepsilon\right)w$ when $w$ is large (depending on $\varepsilon$ ). Several possible generalizations of the problemare also discussed.

Détail

DOI : 10.4153/CMB-2015-073-7

Mots-clés : 05C70, block design, hypergraph

Bibliographie

[1] [1] Chan, J. H., Dukes, P. J., Lamken, E. R., and Ling, A. C. H., The asymptotic existence of resolvable group divisible designs. J. Combin. Des. 21(2013), 112–126. Google Scholar

[2] [2] Chowla, S., P. Erdôs, and Strauss, E. G., On the maximal number ofpairwise orthogonal latinsquares of a given order. Canad. J. Math. 12(1960), 204–208. Google Scholar | DOI

[3] [3] Colbourn, C. J. and Rosa, A., Triple systems.Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1999. Google Scholar

[4] [4] Doyen, J. and Wilson, R. M., EmbeddingsofSteiner triple systems.Discrete Math. 5(1973), 229–239. Google Scholar | DOI

[5] [5] Draganova, A., Asymptotic existence of decompositions of edge-colored graphs and hypergraphs. Ph.D. dissertation, University of California, Los Angeles, 2006. Google Scholar

[6] [6] Dukes, P.J. and Ling, A. C. H., Asymptotic existence of resolvable graph designs. Canad.Math. Bull. 50(2007), no. 4, 504–518. Google Scholar | DOI

[7] [7] Gustavsson, T., Decompositions of large graphs and digraphs with high minimum degree.Doctoral Dissertation, Department of Mathematics, Stockholm University, 1991. Google Scholar

[8] [8] Keevash, P., The existence of designs. arxiv:1401.3665v1. Google Scholar

[9] [9] Lamken, E. R. and Wilson, R. M., Decompositions of edge-colored complete graphs. J. Combin. Theory Ser.A 89(2000), no. 2,149-200. Google Scholar | DOI

[10] [10] Liu, J., Asymptotic existence theorems for frames and group divisible designs.J. Combin. Theory Ser. A 114(2007), no. 3, 410–420. http://dx.doi.0rg/IO.IOI6/j.jcta.2OO6.O6.OO6. Google Scholar

[11] [11] Mendelsohn, E. and Rosa, A., Embedding maximal packings of triples.Congr.Numer. 40(1983), 235–247. Google Scholar

[12] [12] Ray-Chaudhuri, D. K. Wilson, and R.M., The existence of resolvable block designs. In: A Survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), North-Holland, Amsterdam, 1973, pp. 361–376. Google Scholar

[13] [13] Rees, R. and Stinson, D. R., On combinatorial designs with subdesigns. Combinatorial designsâÂîatribute to HaimHanani.Discrete Math. 77(1989), no. 1-3, 259–279. Google Scholar | DOI

[14] [14] Rees, R. and Stinson, D. R., On the existence of incomplete designs of block size four having one hole. Utilitas Math. 35(1989), 119–152. Google Scholar

[15] [15] Stinson, D. R., A new proof of the Doyen-Wilson theorem. J. Austral. Math. Soc. Ser. A 47(1989), no. 1, 32–42. Google Scholar | DOI

[16] [16] van Bommel, C. M., An asymptotic existence theory on incomplete mutually orthogonal latin squares. M.Sc. thesis, University of Victoria, 2015. Google Scholar

[17] [17] Wilson, R. M., An existence theory for pairwise balanced designs. II. The structure of PBD-closed sets and the existence conjectures. J. Combin. Theory Ser. A 13(1972), 246–273. Google Scholar | DOI

[18] [18] Wilson, R. M., An existence theory for pairwise balanced designs. III. Proof of the existence conjectures. J. Combin.Theory Ser.A 18(1975), 71–79. . Google Scholar | DOI

[19] [19] Wilson, R. M., The construction of group divisible designs and partial planes having the maximum number of lines of a given size. In: Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications, Univ. North Carolina, Chapel Hill, N.C. 1970, pp. 488–497. Google Scholar

[20] [20] Wilson, R. M., Constructions and uses ofpairwise balanced designs. In: Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974) Part 1: Theory of designs, finite geometry and coding theory, Math. Centre Tracts, 55, Math. Centrum, Amsterdam, 1974, pp. 18–41. Google Scholar

[21] [21] Wilson, R. M., Decompositions of complete graphs into subgraphs isomorphic to a given graph. In: Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), CongressusNumerantium, 15, Utilitas Math., Winnipeg, Man., 1976, pp. 647–659. Department of Mathematics and Statistics, University of Victoria, Victoria, BC e-mail: [e-mail] Google Scholar