Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

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


Authors: Ted Chinburg, Carla D. Savage and Herbert S. Wilf
Journal: Trans. Amer. Math. Soc. 351 (1999), 379-402
MSC (1991): Primary 11C08, 11L03, 05E99
MathSciNet review: 1487609
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 11C08, 11L03, 05E99

Retrieve articles in all journals with MSC (1991): 11C08, 11L03, 05E99


Additional Information

Ted Chinburg
Affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104-6395
Email: ted@math.upenn.edu

Carla D. Savage
Affiliation: Department of Computer Science, North Carolina State University, Raleigh, North Carolina 27695-8206
Email: cds@cayley.csc.ncsu.edu

Herbert S. Wilf
Affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104-6395
Email: wilf@math.upenn.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-99-02229-1
PII: S 0002-9947(99)02229-1
Keywords: Gray code, nonexistence
Received by editor(s): February 5, 1997
Additional Notes: The first and second authors were supported in part by the National Science Foundation
The third author was supported in part by the Office of Naval Research
Article copyright: © Copyright 1999 American Mathematical Society