Packing sequences
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)].
scientific article; zbMATH DE number 3841882