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

Let S(n) be a collection of subsets of {1,..., n}. In this paper we study n umerical obstructions to the existence of orderings of S(n) for which the c ardinalities 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 d eletion of a single element of{1,..., n}. The cardinalities of successive s ubsets in a Gray code order must alternate in parity. It follows that if cl (S(n)) is the difference between the number of elements of S(n) having even (resp. odd) cardinality, then - 1 is a lower bound for the cardinality of t he complement of any subset of S(n) which can be listed in Gray code order. For g greater than or equal to 2, the collection B(n,g) of g-blockfree subs ets of {1,..., n} is defined to be the set of an subsets S of {1,...,n} suc h that greater than or equal to g if a,b is an element of S and a not equal 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 --> infinity. 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 o f subsets of B(n, g) are proved using generalizations of d(B(n, g)). Howeve r, we will show that for all g, one can order B(n, g) so that successive el ements differ by the adjunction and/or deletion of an integer from {1,..., n}. We show that, over an A-letter alphabet, the words of length n which contai n no block of k consecutive letters cannot, in general, be listed so that s uccessive words differ by a single letter. However, if ic > 2 and A > 2 or if k = 2 and A > 3, such a listing is always possible.