Premium
Constructions of optimal packing designs
Author(s) -
Yin Jianxing,
Assaf Ahmed M.
Publication year - 1998
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/(sici)1520-6610(1998)6:4<245::aid-jcd3>3.0.co;2-f
Subject(s) - combinatorics , mathematics , packing problems , integer (computer science) , block (permutation group theory) , discrete mathematics , computer science , programming language
Let v and k be positive integers. A ( v , k , 1)‐packing design is an ordered pair ( V , B ) where V is a v ‐set and B is a collection of k ‐subsets of V (called blocks) such that every 2‐subset of V occurs in at most one block of B . The packing problem is mainly to determine the packing number P ( k , v ), that is, the maximum number of blocks in such a packing design. It is well known that P ( k , v ) ≤ ⌊ v ⌊( v − 1)/( k − 1)⌋/ k ⌋ = J ( k , v ) where ⌊×⌋ denotes the greatest integer y such that y ≤ x . A ( v , k , 1)‐packing design having J ( k , v ) blocks is said to be optimal. In this article, we develop some general constructions to obtain optimal packing designs. As an application, we show that P (5, v ) = J (5, v ) if v ≡ 7, 11 or 15 (mod 20), with the exception of v ∈ {11, 15} and the possible exception of v ∈ {27, 47, 51, 67, 87, 135, 187, 231, 251, 291}. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 245–260, 1998