Applied Analytic Combinatorics

点击翻译按钮获取中文摘要

Combinatorial structures arising as discrete mathematical models of physical phenomena are increasingly found lurking at the interface of mathematics and other sciences, particularly physics, biology and computer science. The simplicity of the structures is deceptive, as they are often sufficiently rich to play a key role in our understanding of the underlying phenomena being studied. Analytic combinatorics is a rapidly advancing area of theory which studies combinatorial families and their properties using complex analysis and algebra. A central feature of this theory is its algorithmic and generic nature. This research program considers several problems in the domain of statistical mechanics, genomics and theoretical computer science, and to each addresses questions well adapted to analytic combinatorics: solvability; enumeration and parameter distribution; and random generation. Three applications act as conduits of study: (I) lattice path enumeration; (II) tree models of permutations; and (III) RNA secondary structures. The questions take the form of "Do we expect a particular polymer to have this shape?" "What is a typical evolution scenario between two mammals and their common ancestor?" and "How often should this folding structure occur in an RNA strand of this length?". Ideally, we then compare results to actual data in order to gauge the quality of the model. Random generation allows us to form and test hypotheses, to determine the practical complexity of related algorithms, and to assess the quality of the data. The results for each application inform a larger study of combinatorial structures:we are interested in the meta classification of combinatorial classes by some notion of complexity. This augments the classical Chomsky Hierarchy of formal languages.