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

Let be a collection of subsets of . In this paper we study numerical obstructions to the existence of orderings of 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 is a Gray code order if successive subsets differ by the adjunction or deletion of a single element of . The cardinalities of successive subsets in a Gray code order must alternate in parity. It follows that if is the difference between the number of elements of having even (resp. odd) cardinality, then is a lower bound for the cardinality of the complement of any subset of which can be listed in Gray code order. For , the collection of -blockfree subsets of is defined to be the set of all subsets of such that if and . We will construct a Gray code order for . In contrast, for we find the precise (positive) exponential growth rate of with as . This implies is far from being listable in Gray code order if is large. Analogous results for other kinds of orderings of subsets of are proved using generalizations of . However, we will show that for all , one can order so that successive elements differ by the adjunction and/or deletion of an integer from . We show that, over an -letter alphabet, the words of length which contain no block of consecutive letters cannot, in general, be listed so that successive words differ by a single letter. However, if and or if and , such a listing is always possible.