Constructions of optimal packing designs

Jianxing Yin, Ahmed M. Assaf

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

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 ⌊x⌋ 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}.

Original languageEnglish
Pages (from-to)245-260
Number of pages16
JournalJournal of Combinatorial Designs
Volume6
Issue number4
DOIs
StatePublished - 1998

Keywords

  • Construction
  • Optimal packing
  • Packing number

Fingerprint

Dive into the research topics of 'Constructions of optimal packing designs'. Together they form a unique fingerprint.

Cite this