The Knowlton-Graham partition problem

DOI10.1006/JCTA.1996.0015MaRDI QIDQ1906132zbMATH OpenOpenAlexFDO

Authors Donald E. Knuth

Publication date 13 May 1996

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9502237

zbMATH Keywords

0-1 matricescolumn sumsKnowlton-Graham partitionssymmetric matrix

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17)

Abstract: A set partition technique that is useful for identifying wires in cables can be recast in the language of 0--1 matrices, thereby resolving an open problem stated by R.~L. Graham in Volume 1 of this journal. The proof involves a construction of 0--1 matrices having row and column sums without gaps.

Review text

The main purpose of this paper is to resolve an open problem stated by Graham, viz. Knowlton-Graham partitions of order \(m\) do exist for all \(n\) in the range \((\begin{smallmatrix} m+ 1\\ 2\end{smallmatrix})\leq n\leq J(m)\). The proof involves a construction of \(0-1\) matrices having row and column sums without gaps.

Recommendations

• The partition problem
• The \(k\)-partitioning problem
• The satisfactory partition problem
• The partition conjecture
• On a Problem of Partitions
• A Generalization of the Partition Problem
• The mean-partition problem
• A partition problem

Cited in

(2)

• scientific article; zbMATH DE number 3916280 (Why is no real title available?)
• The mean-partition problem

This page was built for publication: The Knowlton-Graham partition problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1906132)