Constructing designs straightforwardly: Worst arising cases
type: Item
instance of: scholarly article
zbMATH Open document ID: 0971.05035
author: Oleg Pikhurko
publication date: 2001-10-21T00:00:00Z
Mathematics Subject Classification ID: 05B40
zbMATH DE Number: 1595940
zbMATH Keywords: covering designs
zbMATH Keywords: packing designs
MaRDI profile type: Publication
cites work: On complete subgraphs of different orders
cites work: Supersaturated graphs and hypergraphs
cites work: Asymptotically optimal covering designs
cites work: Saturated graphs with minimal number of edges
cites work: A class of constructions for Turan's (3,4)-problem
cites work: The Minimum Size of Saturated Hypergraphs
cites work: On a packing and covering problem
cites work: A Remark on the Number of Complete and Empty Subgraphs
cites work: What we know and what we do not know about Turán numbers
cites work: An existence theory for pairwise balanced designs. I: Composition theorems and morphisms
DOI: 10.1002/1520-6610(2001)9:2%3C100::AID-JCD1001%3E3.0.CO;2-W
title: Constructing designs straightforwardly: Worst arising cases
published in: Journal of Combinatorial Designs
review text: A \(t\)-\((v,k,\lambda)\) packing (covering) design \(D\) is a collection of \(k\)-element sets, called blocks, out of a \(v\)-set such that each \(t\)-subset of the \(v\)-set is contained in at most (at least) \(\lambda\) blocks. Generally, one is interested in maximizing (minimizing) the size of a packing (covering) design with given parameters, but other questions may be posed as well. In the current paper, the problems of finding the minimum size of a maximal packing and the maximum size of a minimal covering are considered. A packing is maximal if it is not possible to add further blocks without violating the packing criterion; a minimal covering is defined in an analogous way. The results obtained give worst-case bounds for the sizes of designs constructed, for example, by any greedy algorithm.
reviewed by: Patric R. J. Östergård
description: scientific article