Packing sequences
type: Item
instance of: scholarly article
title: Packing sequences
zbMATH Open document ID: 0531.05019
DOI: 10.1016/0097-3165(84)90003-7
author: Arthur M. Hobbs
published in: Journal of Combinatorial Theory. Series A
publication date: 1984-01-01T00:00:00Z
review text: The author investigates a conjecture of \textit{A. Gyárfás} and \textit{J. Lehel} [Combinatorics, Keszthely 1976, Colloq. Math. János Bolyai 18, 463-469 (1978; Zbl 0389.05030)] (conjecture I) and a related conjecture by himself (conjecture II) as stated below. Conjecture I. If \(s_ 1,s_ 2,...,s_{n-1}\) are sequences of positive integers such that \(s_ i\) has length \(i+1\) and sum 2i for each i, then there is an (n-1) by n matrix M, such that, for each i, row i of M contains O's and a permutation of \(s_ i\), and each column of M sums to n-1. Conjecture II. Let \(s_ 1,s_ 2,...,s_ n\) be sequences of positive integers such that, for each i, \(s_ i\) has length i and sum 2i-1. Then there is an \(n\times n\) matrix M such that, for each i, row i of M contains O's and a permutation of \(s_ i\), and each column of M sums to n. It is shown by a graph-theoretic packing of trees into \(K_ n\), the complete graph on n vertices, that these conjectures are true for a very large number of sequences \(\{s_ i\}\). The author points out that subsequent to his work, Conjectures I and II were proved by \textit{P. C. Fishburn} [ J. Combin. Theory, Ser. A 34, 98-101 (1983; Zbl 0504.05024)].
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 3841882
zbMATH Keywords: (0,1)-matrices
zbMATH Keywords: packing of trees into \(K_ n\)
zbMATH Keywords: sequences
MaRDI profile type: Publication
full work available at URL: 0097-3165(84)90003-7
OpenAlex ID: W4212862480
cites work: Q4187840
cites work: Q4170743
cites work: Packing trees in complete graphs
cites work: Q3919751
cites work: Balanced integer arrays: a matrix packing theorem
description: scientific article; zbMATH DE number 3841882