Séminaire Lotharingien de Combinatoire, 80B.16 (2018), 11 pp.

James Propp

One-Dimensional Packing: Maximality Implies Rationality

Abstract. Every set of natural numbers determines a generating function convergent for q in (-1,1) whose behavior as q -> 1- determines a germ. These germs admit a natural partial ordering that can be used to compare sizes of sets of natural numbers in a manner that generalizes both cardinality of finite sets and density of infinite sets. For any finite set D of positive integers, call a set S "D-avoiding" if no two elements of S differ by an element of D. It is shown that any D-avoiding set that is maximal in the class of D-avoiding sets (with respect to germ-ordering) is eventually periodic. This implies an analogous result for packings in N. It is conjectured that for all finite D there is a unique maximal D-avoiding set.

Received: November 14, 2017. Accepted: February 17, 2018. Final version: April 1, 2018.

The following versions are available: