The Existence of Kirkman Squares—Doubly Resolvable (v,3,1)-BIBDs
Tóm tắt
A Kirkman square with index λ, latinicity μ, block size k, and v points, KS
k
(v;μ,λ), is a t×t array (t=λ(v−1)/μ(k−1)) defined on a v-set V such that (1) every point of V is contained in precisely μ cells of each row and column, (2) each cell of the array is either empty or contains a k-subset of V, and (3) the collection of blocks obtained from the non-empty cells of the array is a (v, k,λ)-BIBD. For μ=1, the existence of a KS
k
(v; μ, λ) is equivalent to the existence of a doubly resolvable (v, k, λ)-BIBD. The spectrum of KS
2 (v; 1, 1) or Room squares was completed by Mullin and Wallis in 1975. In this paper, we determine the spectrum for a second class of doubly resolvable designs with λ=1. We show that there exist KS
3 (v; 1, 1) for
$$v \equiv 3{\text{ (mod 6)}}$$
, v=3 and v≥27 with at most 23 possible exceptions for v.
Tài liệu tham khảo
R. Julian R. Abel, Some new BIBDs with block size 7, J. Combinatorial Designs, Vol. 8 (2000) pp. 146–150.
R. Julian R. Abel, A. E. Brouwer, C. J. Colbourn and J. H. Dinitz, Mutually orthogonal Latin squares (MOLS), In (C. J. Colbourn, J. H. Dinitz, eds.), The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL (1996) pp. 111–142.
R. Julian R. Abel and S. C. Furino, Resolvable and near resolvable designs, In (C. J. Colbourn, J. H. Dinitz, eds.), The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL (1996) pp. 87–94.
I. Anderson, Combinatorial Designs, Construction Methods, Ellis Horwood, Limited, Chichester, England (1990).
R. D. Baker, Orthogonal line packings of PG 2m-1 (2), J. Combinat. Theory (A), Vol. 36 (1984) pp. 245–248.
F. E. Bennett, H-D. O. F. Gronau, A. C. H. Ling and R. C. Mullin, PBD closure, In (C. J. Colbourn, J. H. Dinitz, eds.), The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL (1996) pp. 203–213.
T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press (1986).
C. J. Colbourn and A. Rosa, Triple Systems, Oxford University Press, Oxford, UK (1999).
C. J. Colbourn and S. A. Vanstone, Doubly resolvable twofold triple systems, In Proc. Eleventh Manitoba Conf. Numer. Math. Computing, Congressus Numerantium, Vol. 34 (1982) pp. 219–223.
C. J. Colbourn, D. Curran and S. A. Vanstone, Recursive constructions for Kirkman squares with block size 3, Utilitas Math., Vol. 32 (1987) pp. 169–174.
D. G. Curran and S. A. Vanstone, Doubly resolvable designs from generalized Bhaskar Rao designs, Discrete Mathematics, Vol. 73 (1988) pp. 49–63.
J. H. Dinitz and D. R. Stinson, Room squares and related designs, In Contemporary Design Theory: A Collection of Surveys, Wiley, New York (1992) pp. 137–204.
R. Fuji-Hara and S. A. Vanstone, On the spectrum of doubly resolvable designs, Congressus Numer (1980) pp. 399–407.
R. Fuji-Hara and S. A. Vanstone, The existence of orthogonal resolutions of lines in AG(n, q), J. Combinatorial Theory (A), Vol. 45 (1987) pp. 139–147.
R. Fuji-Hara and S. A. Vanstone, Transversal designs and doubly resolvable designs, Europ. J. Combin., Vol. 1 (1980) pp. 219–223.
S. C. Furino, Y. Miao and J. Yin, Frames and Resolvable Designs, CRC Press, Boca Raton, FL (1996).
H. Hanani, Balanced incomplete block designs and related designs, Discrete Math. (1975) pp. 253–369.
Z. Janko and V. D. Tonchev, New designs with block size 7, J. Combin. Theory (A), Vol. 83 (1998) pp. 152–157.
T. P. Kirkman, Query VI, Lady's and Gentleman Diary (1850) p. 48.
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, CRC Press, Boca Raton, FL (1998).
E. R. Lamken, 3-complementary frames and doubly near resolvable (v, 3, 2)-BIBDs, Discrete Math., Vol. 88 (1991) pp. 59–78.
E. R. Lamken, Constructions for generalized balanced tournament designs, Discrete Mathematics, Vol. 131 (1994) pp. 127–151.
E. R. Lamken, Constructions for resolvable and near resolvable (v, k, λ)-BIBDs, In (D. K. Ray-Chaudhuri, ed.) Coding Theory and Design Theory, Part II: Design Theory, Springer-Verlag, New York (1990) pp. 236–250.
E. R. Lamken, Coverings, Orthogonally Resolvable Designs and Related Combinatorial Configurations, Ph.D. Thesis, University of Michigan (1983).
E. R. Lamken, Designs with orthogonal resolutions and decompositions of edge-colored complete graphs, in preparation.
E. R. Lamken, The existence of doubly resolvable (v, 3, 2)-BIBDs, J. Combin. Theory (A), Vol. 72 (1995) pp. 50–76.
E. R. Lamken, The existence of KS 3 (v; 2, 4)s, Discrete Math., Vol. 186 (1998) pp. 195–216.
E. R. Lamken, Generalized balanced tournament designs, Transactions of the AMS, Vol. 318 (1990) pp. 473–490.
E. R. Lamken and S. A. Vanstone, Existence results for doubly near resolvable (v, 3, 2)-BIBDs, Discrete Math., Vol. 120 (1993) pp. 135–148.
E. R. Lamken and S. A. Vanstone, The existence of KS k(v; µ, λ): I. the main constructions, Utilitas Math., Vol. 27 (1985) pp. 111–130.
E. R. Lamken and S. A. Vanstone, The existence of KS k (v; µ, λ): II. special constructions, Utilitas Math., Vol. 27 (1985) pp. 131–155.
E. R. Lamken and S. A. Vanstone, On a class of Kirkman squares of index 2, J. of Australian Math. Society (A), Vol. 44 (1988) pp. 33–41.
A. C. H. Ling, X. J. Zhu, C. J. Colbourn and R. C. Mullin, Pairwise balanced designs with consecutive block sizes, Des. Codes Crypt., Vol. 10 (1997) pp. 203–222.
J. Lu, An existence theory for resolvable balanced incomplete block designs, Acta Math. Sinica, Vol. 27 (1984) pp. 458–468 (in Chinese).
R. Mathon and S. A. Vanstone, Doubly resolvable Kirkman systems, Congressus Num., Vol. 29 (1980) pp. 611–125.
R. Mathon and S. A. Vanstone, On the existence of doubly resolvable Kirkman systems and equidistant permutation arrays, Discrete Math., Vol. 30 (1980) pp. 157–172.
R. C. Mullin and W. D. Wallis, The existence of Room squares, Aequationes Math., Vol. 1 (1975) pp. 1–7.
A. V. Nazarok, Orthogonal starters and multidimensional Kirkman hypercubes, Discrete Math. Appl., Vol. 5 (1996) pp. 541–545.
A. V. Nazarok, On the existence of multidimensional Kirkman hypercubes of a certain class, (Ukranian), Dopov./Dokl. Akad. Nauk Ukraini, Vol. 7 (1993) pp. 34–35.
A. Rosa and S. A. Vanstone, Starter-adder techniques for Kirkman squares and Kirkman cubes of small sides, Ars Combinatoria, Vol. 14 (1982) pp. 199–212.
A. Rosa and S. A. Vanstone, On the existence of strong Kirkman cubes of order 39 and block size 3, Ann. of Discrete Math., Vol. 26 (1983) pp. 309–320.
D. R. Stinson and S. A. Vanstone, A Kirkman square of order 51 and block size 3, Discrete Mathematics, Vol. 35 (1985) pp. 107–111.
V. D. Tonchev and S. A. Vanstone, On Kirkman triple systems of order 33, Discrete Math., Vol. 106/107 (1992) pp. 493–496.
S. A. Vanstone, Doubly resolvable designs, Discrete Mathematics, Vol. 29 (1980) pp. 77–86.
S. A. Vanstone, On mutually orthogonal resolutions and near resolutions, Ann. of Discrete Mathematics, Vol. 15 (1982) pp. 357–369.
R. M. Wilson, Constructions and uses of pairwise balanced designs, In (M. Hall, Jr and J. H. van Lint, eds.), Proc. NATO Advanced Study Institute in Combinatorics, Nijenrode Castle, Breukelen (1974) pp. 19–42.