Packing of partial designs
type: Item
instance of: scholarly article
title: Packing of partial designs
zbMATH Open document ID: 0797.05008
DOI: 10.1007/BF01202465
author: Noga Alon
published in: Graphs and Combinatorics
publication date: 1994-10-10T00:00:00Z
review text: Two hypergraphs \(H_ 1\) and \(H_ 2\) each with \(v\) vertices can be packed if there are edge disjoint hypergraphs \(H_ 1'\) and \(H_ 2'\) on the same set \(V\) of vertices where \(H_ i'\) is isomorphic to \(H_ i\). It was proven by \textit{B. Ganter, J. Pelikan} and \textit{L. Teirlinck} [Ars Comb. 4, 133-142 (1977; Zbl 0418.05003)] that if \(k\geq 2t\), then every two \((t,k,v)\) partial designs can be packed. In this paper it is shown that for any fixed integers \(k\) and \(t\) with \(t\leq k\leq 2t-2\) and for all sufficiently large \(v\), there are two \((t,k,v)\) partial designs that cannot be packed. Moreover, there are two isomorphic partial \((t,k,v)\)- designs that cannot be packed. It is also shown that for every fixed \(k\geq 2t-1\) and for all sufficiently large \(v\), there is a \((\lambda_ 1,t,k,v)\) partial design and a \((\lambda_ 2,t,k,v)\) partial design that cannot be packed, where \(\lambda_ 1\lambda_ 2\leq O(v^{k-2t+1}\log v)\). Both results are nearly optimal asymptotically and answer questions of Teirlinck. The proofs are probabilistic.
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 567479
zbMATH Keywords: packing
zbMATH Keywords: hypergraphs
zbMATH Keywords: partial designs
reviewed by: J. H. Dinitz
MaRDI profile type: Publication
cites work: The probabilistic method
cites work: Packings of graphs and applications to computational complexity
cites work: Q4830805
cites work: Subgraphs of graphs. I
cites work: Constructions of Disjoint Steiner Triple Systems
cites work: Q3208661
cites work: On a packing and covering problem
cites work: Edge disjoint placement of graphs
cites work: A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
cites work: On making two Steiner triple systems disjoint
full work available at URL: https://doi.org/10.1007/bf01202465
OpenAlex ID: W2022127754
description: scientific article; zbMATH DE number 567479