Thomas Prellberg is Professor of Mathematics at Queen Mary University of London. His research interests are lattice statistical mechanics, enumerative and asymptotic combinatorics, dynamical systems, Monte Carlo algorithms, and soft condensed matter.
Éric Fusy works in enumerative combinatorics and algorithmics on combinatorial structures.
Erik Panzer is an expert on using hyperlogarithms to evaluate Feynman integrals.
Christine Heitsch works at the interface between discrete mathematics and molecular biology.
- Random generation of combinatorial structures
- Éric Fusy
We will give a survey of different methods for the random generation of combinatorial structures such as, for instance, permutations, paths, words, trees, graphs, polyominos, and tilings. These structures have typically a size-parameter n (such as the number of nodes in trees, the number of steps in paths,...), and a random sampling algorithm is to receive as input the desired size n, and to output a (uniformly) random structure of that size. Efficiency is crucial, since a motivation for random sampling is to observe the behaviour of large random structures; we will see that it is often possible to randomly sample with a low complexity in n (say, linear, or polynomial of small degree).
The methods we discuss have a strong combinatorial flavor, in the sense that they arise from counting methods, and/or that the performance of such samplers can be analysed by counting methods. We will discuss in particular the case of Catalan structures, where various techniques (in particular the cyclic lemma) can be used, resulting in exact-size random samplers of linear time complexity.
We will also discuss two methods that apply in greater generality, in the setting of decomposable combinatorial structures: (i) the recursive method that is based on the counting coefficients, and (ii) Boltzmann samplers that are based on generating functions, with the advantage that the complexity of generation is linear when relaxing the constraint of fixed-size sampling.
- From Rosenbluth Sampling to PERM - rare event sampling with stochastic growth algorithms
We discuss uniform sampling algorithms that are based on stochastic growth methods, using sampling of extreme configurations of polymers in simple lattice models as a motivation. We shall show how a series of clever enhancements to a fifty-odd year old algorithm, the Rosenbluth method, led to a cutting-edge algorithm capable of uniform sampling of equilibrium statistical mechanical systems of polymers in situations where competing algorithms failed to perform well. Examples range from collapsed homo-polymers near sticky surfaces to models of protein folding.
Beyond the motivational setting of polymers, these algorithms can be of general interest to combinatorialists, as one can compute approximate answers to questions of enumerative combinatorics. This is for example helpful when one wants to formulating conjectures (or is looking for evidence to refute conjectures) on asymptotic growth rates.
For the tutorials, it will be helpful if students have some basic background in C, to the extent that they can read and manipulate simple code.
- Combinatorial Hopf algebras in particle physics
- Erik Panzer
Hopf algebras are extremely powerful tools to formulate combinatorial identities and proofs. Research in this subject is currently very active and the literature has been growing considerably. As an invitation to this area, we follow the day of a particle physicist and his encounters with Hopf algebras.
Assuming only basic knowledge of linear algebra, this course starts off with a short introduction to combinatorial Hopf algebras. With the important example of rooted trees we shall study the combinatorics of renormalization in a quantum field theory. We will meet Dyson-Schwinger equations, which are generating functions for physical observables.
Furthermore, we will point out Hopf algebras that enter particle physics in a completely different way, namely in the computation of Feynman integrals. Here, Hopf algebras provide an interface between analysis and combinatorics. This will become clear through a primer on iterated integrals and polylogarithms.
- Strings, Trees, and RNA Folding
- Christine Heitsch
By their nature, biological sequences are often abstracted to combinatorial structures: strings over finite alphabets and their representation as trees and other graphs. The interaction between discrete mathematics and molecular biology has been especially fruitful in the case of RNA secondary structures due to the thermodynamics of the Watson-Crick base pairings.
An RNA molecule is a linear biochemical chain which folds into a three dimensional structure via a set of 2D base pairings known as a secondary structure. Despite significant advances over the past 25 years, RNA secondary structure prediction remains a fundamental open problem in computational molecular biology. This tutorial will address some of the many combinatorial results both motivated by and with applications to questions about the base pairing of RNA sequences.
In one direction, combinatorics has been successfully applied to many important problems in RNA secondary structure analysis, including enumeration, comparison, classification, and motif identification. One question of significant current interest is the parametric analysis of RNA secondary structure prediction. This addresses the dependence of prediction results on the underlying model parameters. As will be illustrated, geometric combinatorics can be used to analyze the trade-offs among different loop structures as a function of free energy parameters in the nearest neighbor thermodynamic model via a folding polytope and its normal fan.
In the other direction, questions about RNA secondary structures motivate new combinatorial theorems. In this case, we focus on the connection with meander enumeration. A meander can be considered as two maximally different noncrossing perfect matchings which form a single closed loop. Although meanders occur in a variety of mathematical settings, from combinatorial models of polymer folding to the Temperley-Lieb algebra, their exact enumeration is still an open problem. As we will explain, extending results for plane trees and noncrossing partitions motivated by the biology of RNA folding suggest new approaches to the combinatorics of meander enumeration.
Problems and projects
As well as the courses, students will work in groups on projects, expanding their exploration of the topics in the courses. One of the goals of the program is to bring out open problems which ought to be better known to a wider part of the combinatorial community.
Overall this program is suitable for graduate students in combinatorics as well as those outside combinatorics who are interested in using combinatorial tools in their work.
- T. Prellberg, "From Rosenbluth Sampling to PERM - rare event sampling with stochastic growth algorithms," in R. Leidl and A. K. Hartmann (eds), Modern Computational Science 12: Lecture Notes from the 4th International Oldenburg Summer School, pages 311-334, BIS-Verlag der Carl von Ossietzky Universität Oldenburg, 2012
- Erik Panzer, "Renormalization, Hopf algebras and Mellin transforms
- Erik Panzer, "Algorithms for the symbolic integration of hyperlogarithms with applications to Feynman integrals