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: