Angelika STEGER
On Boltzmann samplers and properties of combinatorial structures
In the past decades the G(n,p) model of random graphs, introduced by Erdős and Rényi in the 60's, has led to numerous beautiful and deep results. A key feature that is used in basically all proofs is that edges in G(n,p) appear independently. This situation changes dramatically if one considers graph classes with structural side constraints. For example, in a random planar graph Pn (a graph drawn uniformly at random from the class of all labeled planar graphs on n vertices) the edges are obviously far from being independent. In this talk we show that recent progress in the construction of Boltzmann samplers can be used to reduce the study of properties of combinatorial objects to properties of sequences of independent and identically distributed random variables -- to which we can then again apply well known machinery from random graph theory.
On Boltzmann samplers and properties of combinatorial structures
In the past decades the G(n,p) model of random graphs, introduced by Erdős and Rényi in the 60's, has led to numerous beautiful and deep results. A key feature that is used in basically all proofs is that edges in G(n,p) appear independently. This situation changes dramatically if one considers graph classes with structural side constraints. For example, in a random planar graph Pn (a graph drawn uniformly at random from the class of all labeled planar graphs on n vertices) the edges are obviously far from being independent. In this talk we show that recent progress in the construction of Boltzmann samplers can be used to reduce the study of properties of combinatorial objects to properties of sequences of independent and identically distributed random variables -- to which we can then again apply well known machinery from random graph theory.