Combinatorial families that are exponentially far from being listable in Gray code sequence

Abstract:

Let $S(n)$ be a collection of subsets of $\{1,...,n\}$. In this paper we study numerical obstructions to the existence of orderings of $S(n)$ for which the cardinalities of successive subsets satisfy congruence conditions. Gray code orders provide an example of such orderings. We say that an ordering of $S(n)$ is a Gray code order if successive subsets differ by the adjunction or deletion of a single element of $\{1,\ldots ,n\}$. The cardinalities of successive subsets in a Gray code order must alternate in parity. It follows that if $d(S(n))$ is the difference between the number of elements of $S(n)$ having even (resp. odd) cardinality, then $|d(S(n))| - 1$ is a lower bound for the cardinality of the complement of any subset of $S(n)$ which can be listed in Gray code order. For $g \ge 2$, the collection $B(n,g)$ of $g$-blockfree subsets of $\{1,\ldots ,n\}$ is defined to be the set of all subsets $S$ of $\{1,\ldots ,n\}$ such that $|a-b| \ge g$ if $a,b \in S$ and $a \ne b$. We will construct a Gray code order for $B(n,2)$. In contrast, for $g > 2$ we find the precise (positive) exponential growth rate of $d(B(n,g))$ with $n$ as $n \to \infty$. This implies $B(n,g)$ is far from being listable in Gray code order if $n$ is large. Analogous results for other kinds of orderings of subsets of $B(n,g)$ are proved using generalizations of $d(B(n,g))$ . However, we will show that for all $g$, one can order $B(n,g)$ so that successive elements differ by the adjunction and/or deletion of an integer from $\{1,\ldots ,n\}$. We show that, over an $A$-letter alphabet, the words of length $n$ which contain no block of $k$ consecutive letters cannot, in general, be listed so that successive words differ by a single letter. However, if $k>2$ and $A>2$ or if $k=2$ and $A>3$, such a listing is always possible.