Downloads & Free Reading Options - Results

This grant from the Air Force Office of Scientific Research supported the research related to the two IMA Workshops Finite Markov Chain Renaissance held on October 18-22, 1993 and Random Discrete Structures held on November 15- 19, 1993. The first workshop was organized by Persi Diaconis and David Aldous, while the second one by David Aldous and Robin Pemantle. Both workshops were integral parts of the IMA 1993-1994 year-long program on 'EMERGING APPLICATIONS OF PROBABILITY'. The October workshop addressed the following issues: Theoretical computer science examples: successes and open problems; computation- Bayesian statistics; Classical probability examples: successes and open problems; Mathematical theory and other aspects of Markov Chains. The November workshop explored examples from Jung's work on synchronicity to recent studies of parapsychology; random graphs; random permutations and Stein's method. In addition this workshop addressed new questions concerning probability on discrete infinite structures. The services of J. Michael Steele, a senior fellow was partially supported by this grant. Steele provided over-all direction for the entire probability program. Similarity, the grant supported 8 one-month visitors and 21 workshop participants. Grant AF/F49620-94-1-009 also supported the publication of the technical research reports submitted by the workshop participants for inclusion in the IMA Preprint Series, and two IMA proceedings Volumes. Random discrete structures, Theoretical computer science, Bayesian statistics, Classification probability, Markov chains, Jung's work on synchronicity, Random graphs, Random permutations

We study a model of random $\mathcal{R}$-enriched trees that is based on weights on the $\mathcal{R}$-structures and allows for a unified treatment of a large family of random discrete structures. We establish distributional limits describing local convergence around fixed and random points in this general context, limit theorems for component sizes when $\mathcal{R}$ is a composite class, and a Gromov--Hausdorff scaling limit of random metric spaces patched together from independently drawn metrics on the $\mathcal{R}$-structures. Our main applications treat a selection of examples encompassed by this model. We consider random outerplanar maps sampled according to arbitrary weights assigned to their inner faces, and classify in complete generality distributional limits for both the asymptotic local behaviour near the root-edge and near a uniformly at random drawn vertex. We consider random connected graphs drawn according to weights assigned to their blocks and establish a Benjamini--Schramm limit. We also apply our framework to recover in a probabilistic way a central limit theorem for the size of the largest $2$-connected component in random graphs from planar-like classes. We prove Benjamini--Schramm convergence of random $k$-dimensional trees and establish both scaling limits and local weak limits for random planar maps drawn according to Boltzmann-weights assigned to their $2$-connected components.

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long-standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. The theorem of Schacht can be applied in a more general setting and yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erdos and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting that is somewhat more general and stronger than the one obtained by Conlon and Gowers. We then use this theorem to derive several new results, among them a random version of the Erdos-Simonovits stability theorem for arbitrary graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.

We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemer\'edi's theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions and we determine the threshold for Tur\'an-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, \L uczak, and R\"odl for Tur\'an-type problems in random graphs. Similar results were obtained by Conlon and Gowers.

We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemer\'edi's theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions and we determine the threshold for Tur\'an-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, \L uczak, and R\"odl for Tur\'an-type problems in random graphs. Similar results were obtained by Conlon and Gowers.