Probability

Laplacians and connections

Speaker: 
Rick Kenyon
Date: 
Mon, Jun 25, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

We discuss the Laplacian operator on vector bundles on graphs, in particular relating its determinant to the enumeration of "cycle-rooted spanning forests" which are combinatorial objects generalizing spanning trees.

Class: 

Sharp Benefit-to-Cost Rules for the Evolution of Cooperation on Regular Graphs

Speaker: 
Yu-ting Chen
Date: 
Mon, Jun 25, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

We study two of the simple rules on finite graphs under the death-birth updating and the imitation updating discovered by Ohtsuki, Hauert, Lieberman, and Nowak [Nature, 441 (2006) 502-505]. Each rule specifies a payoff-ratio cutoff point for the magnitude of fixation probabilities of the underlying evolutionary game between cooperators and defectors. We view the Markov chains associated with the two updating mechanisms as voter model perturbations. Then we present a first-order approximation for fixation probabilities of general voter model perturbations on finite graphs subject to small perturbation in terms of the voter model fixation probabilities. In the context of regular graphs, we obtain algebraically explicit first-order approximations for the fixation probabilities of cooperators distributed as certain uniform distributions. These approximations lead to a rigorous proof that both of the rules of Ohtsuki et al. are valid and are sharp.

Class: 

Interacting Particle Systems 13

Speaker: 
Omer Angel
Date: 
Mon, Jun 25, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

Particles attempt to follow a simple dynamic (random walk, constant flow, etc) in some space (interval, line, cycle, arbitrary graph). Add a simple interaction between particles, and the behaviour can change completely. The resulting dynamical systems are far more complex than the ingredients suggest. These processes (interchange process, TASEP, sorting networks, etc) have diverse to many topics: growth processes, queuing theory, representation theory, algebraic combinatorics. I will discuss recent progress on and open problems arising from several models of interacting particle systems.

Class: 

Random Maps 14

Speaker: 
Gregory Miermont
Date: 
Tue, Jun 26, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

The study of maps, that is of graphs embedded in surfaces, is a popular subject that has implications in many branches of mathematics, the most famous aspects being purely graph-theoretical, such as the four-color theorem. The study of random maps has met an increasing interest in the recent years. This is motivated in particular by problems in theoretical physics, in which random maps serve as discrete models of random continuum surfaces. The probabilistic interpretation of bijective counting methods for maps happen to be particularly fruitful, and relates random maps to other important combinatorial random structures like the continuum random tree and the Brownian snake. This course will survey these aspects and present recent developments in this area.

Class: 

Invariant Matching

Speaker: 
Alexander Holroyd
Date: 
Fri, Jun 22, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

Suppose that red and blue points occur as independent point processes in Rd, and consider translation-invariant schemes for perfectly matching the red points to the blue points. (Translation-invariance can be interpreted as meaning that the matching is constructed in a way that does not favour one spatial location over another). What is best possible cost of such a matching, measured in terms of the edge lengths? What happens if we insist that the matching is non-randomized, or if we forbid edge crossings, or if the points act as selfish agents? I will review recent progress and open problems on this topic, as well as on the related topic of fair allocation. In particular I will address some surprising new discoveries on multi-colour matching and multi-edge matching.

Class: 

Interacting Particle Systems 12

Speaker: 
Omer Angel
Date: 
Fri, Jun 22, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

Particles attempt to follow a simple dynamic (random walk, constant flow, etc) in some space (interval, line, cycle, arbitrary graph). Add a simple interaction between particles, and the behaviour can change completely. The resulting dynamical systems are far more complex than the ingredients suggest. These processes (interchange process, TASEP, sorting networks, etc) have diverse to many topics: growth processes, queuing theory, representation theory, algebraic combinatorics. I will discuss recent progress on and open problems arising from several models of interacting particle systems.

Class: 

Random Maps 12

Speaker: 
Gregory Miermont
Date: 
Fri, Jun 22, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

The study of maps, that is of graphs embedded in surfaces, is a popular subject that has implications in many branches of mathematics, the most famous aspects being purely graph-theoretical, such as the four-color theorem. The study of random maps has met an increasing interest in the recent years. This is motivated in particular by problems in theoretical physics, in which random maps serve as discrete models of random continuum surfaces. The probabilistic interpretation of bijective counting methods for maps happen to be particularly fruitful, and relates random maps to other important combinatorial random structures like the continuum random tree and the Brownian snake. This course will survey these aspects and present recent developments in this area.

Class: 

Random Maps 8

Speaker: 
Gregory Miermont
Date: 
Fri, Jun 15, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

The study of maps, that is of graphs embedded in surfaces, is a popular subject that has implications in many branches of mathematics, the most famous aspects being purely graph-theoretical, such as the four-color theorem. The study of random maps has met an increasing interest in the recent years. This is motivated in particular by problems in theoretical physics, in which random maps serve as discrete models of random continuum surfaces. The probabilistic interpretation of bijective counting methods for maps happen to be particularly fruitful, and relates random maps to other important combinatorial random structures like the continuum random tree and the Brownian snake. This course will survey these aspects and present recent developments in this area.

Class: 

Cover times for sequences of random walks on random graphs

Speaker: 
Yoshihiro Abe
Date: 
Thu, Jun 21, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

We can classify cover times for sequences of random walks on random graphs into two types: One type is the class of cover times approximated by the maximal hitting times scaled by the logarithm of the size of vertex sets. The other type is the class of cover times approximated by the maximal hitting times. These types are characterized by the volume, effective resistances, and geometric properties of random graphs. We classify some examples, such as the supercritical Galton-Watson family trees and the incipient infinite cluster for the critical Galton-Watson family tree.

Class: 

Lebesgue approximation of $(2,\beta)$-superprocesses

Speaker: 
Xin He
Date: 
Thu, Jun 21, 2012
Location: 
PIMS, University of British Columbia
Conference: 
PIMS-MPrime Summer School in Probability
Abstract: 

Let $\xi=(\xi_t)$ be a locally finite $(2,\beta)$-superprocess in $\RR^d$ with $\beta<1$ and $d>2/\beta$. Then for any fixed $t>0$, the random measure $\xi_t$ can be a.s. approximated by suitably normalized restrictions of Lebesgue measure to the $\varepsilon$-neighborhoods of ${\rm supp}\,\xi_t$. This extends the Lebesgue approximation of Dawson-Watanabe superprocesses. Our proof is based on a truncation of $(\alpha,\beta)$-superprocesses and uses bounds and asymptotics of hitting probabilities.

Class: 

Pages