Overview of some general results in combinatorial enumeration

Abstract

This survey article is devoted to general results in combinatorial enumeration. The first part surveys results on growth of hereditary properties of combinatorial structures. These include permutations, ordered and unordered graphs and hypergraphs, relational structures, and others. The second part advertises five topics in general enumeration: 1. counting lattice points in lattice polytopes, 2. growth of context-free languages, 3. holonomicity (i.e., P-recursiveness) of numbers of labeled regular graphs, 4. frequent occurrence of the asymptotics cn^{-3/2}r^n and 5. ultimate modular periodicity of numbers of MSOL-definable structures.

Submitted, minus Section 3.4, to the proceedings of the conference Permutation Patterns 2007. 42 pages

References in corpus (10)

• Small permutation classes
• On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia
• Groups of Intermediate Growth: an Introduction for Beginners
• Some relational structures with polynomial growth and their associated algebras
• The Profile of relations
• The number of hypergraphs and colored Hypergraphs with hereditary properties
• On the growth rate of minor-closed classes of graphs
• Spectra of monadic second order sentences
• Automatic enumeration of regular objects
• On growth rates of permutations, set partitions, ordered graphs and other objects

Cited by in corpus (11)

• Small permutation classes
• Permutation classes of every growth rate above 2.48188
• Pattern avoidance is not P-recursive
• The orbit algebra of a permutation group with polynomial profile is Cohen-Macaulay
• Inflations of geometric grid classes of permutations
• Monadic stability and growth rates of $\omega$-categorical structures
• What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I
• Classification of P-oligomorphic groups, conjectures of Cameron and Macpherson
• Large infinite antichains of permutations
• On the effective and automatic enumeration of polynomial permutation classes
• Effective formulas for linear recurrence sequences of integers