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
DOI: https://doi.org/10.1090/S0002-9947-99-02229-1
MathSciNet review: 1487609
Full-text PDF Free Access

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.

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

• 1. S. J. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs - a survey, Discrete Math. 156 (1996), 1-18. MR 97f:05083
• 2. N. I. Fel'dman, A certain inequality that is connected with linear forms of logarithms of algebraic numbers, (Russian), Dokl. Akad. Nauk. SSSR 207 (1972), 41-43. MR 47:1755
• 3. R. J. Gould, Updating the Hamiltonian problem - a survey, Journal of Graph Theory 15, No. 2 (1991), 121 -157. MR 92m:05128
• 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, Journal of Combinatorial Theory A 30 (1981) 183-208. MR 82g:05007
• 6. C. D. Savage, A survey of combinatorial Gray codes, SIAM Review, 39, No. 4, to appear Dec. 1997. CMP 98:06
• 7. M. B. Squire, Gray codes for A-free strings, Electronic Journal of Combinatorics 3, R17 (1996). MR 97j:68106
• 8. H. S. Wilf, Combinatorial Algorithms: An Update, SIAM, Philadelphia, 1989. MR 90g:05002

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

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: https://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