CPL - Chalmers Publication Library

# Accessibility percolation and first-passage percolation on the hypercube

Anders Martinsson (Institutionen för matematiska vetenskaper, matematik)
Göteborg : Chalmers University of Technology, 2015. - 126 s.
[Licentiatavhandling]

In this thesis, we consider two percolation models on the n-dimensional binary hypercube, known as accessibility percolation and first-passage percolation. First-passage percolation randomly assigns non-negative weights, called passage times, to the edges of a graph and considers the minimal total weight of a path between given end-points. This quantity is called the first-passage time. Accessibility percolation is a biologically inspired model which has appeared in the mathematical literature only recently. Here, the vertices of a graph are randomly assigned heights, or fitnesses, and a path is considered accessible if strictly ascending. We let $\mathbf{\hat{0}}$ and $\mathbf{\hat{1}}$ denote the all zeroes and all ones vertices respectively.

A natural simplification of both models is the restriction to oriented paths, i.e. paths that only flip 0:s to 1:s. Paper I considers the existence of such accessible paths between $\mathbf{\hat{0}}$ and $\mathbf{\hat{1}}$ for fitnesses assigned according to the so-called House-of-Cards and Rough Mount Fuji models. In Paper II we consider the first-passage time between $\mathbf{\hat{0}}$ and $\mathbf{\hat{1}}$ in the case of independent standard exponential passage times. It is previously known that, in the oriented case, this quantity tends to 1 in probability as n tends to infinity. We show that without this restriction, the limit is instead $\ln(1+\sqrt{2})\approx 0.88$. By adapting ideas in Paper II to unoriented accessibility percolation, we are able to determine a limiting probability for the existence of accessible paths from $\mathbf{\hat{0}}$ to the global fitness maximum. This is presented in Paper III.

Nyckelord: hypercube, percolation, accessible path, house of cards, rough mount Fuji, first-passage percolation, Richardson's model, branching translation process

CPL Pubid: 211700

# Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

# Examination

Datum: 2015-02-20
Tid: 10:15
Lokal: Pascal
Opponent: Klas Markström