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 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.

**1.**Stephen J. Curran and Joseph A. Gallian,*Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey*, Discrete Math.**156**(1996), no. 1-3, 1–18. MR**1405010**, 10.1016/0012-365X(95)00072-5**2.**N. I. Fel′dman,*A certain inequality that is connected with linear forms of logarithms of algebraic numbers*, Dokl. Akad. Nauk SSSR**207**(1972), 41–43 (Russian). MR**0313200****3.**Ronald J. Gould,*Updating the Hamiltonian problem—a survey*, J. Graph Theory**15**(1991), no. 2, 121–157. MR**1106528**, 10.1002/jgt.3190150204**4.**F. Gray, Pulse code communication, U. S. Patent 2632058 (1953).**5.**L. J. Guibas and A. M. Odlyzko,*String overlaps, pattern matching, and nontransitive games*, J. Combin. Theory Ser. A**30**(1981), no. 2, 183–208. MR**611250**, 10.1016/0097-3165(81)90005-4**6.**C. D. Savage, A survey of combinatorial Gray codes,*SIAM Review*,**39**, No. 4, to appear Dec. 1997. CMP**98:06****7.**Matthew B. Squire,*Gray codes for 𝐴-free strings*, Electron. J. Combin.**3**(1996), no. 1, Research Paper 17, approx. 29 pp. (electronic). MR**1385319****8.**Herbert S. Wilf,*Combinatorial algorithms: an update*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 55, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR**993775**

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

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