CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

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.

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 and 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 and 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 and 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 . 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 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

Denna post skapades 2015-01-29.
CPL Pubid: 211700


Institutioner (Chalmers)

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


Diskret matematik
Sannolikhetsteori och statistik

Chalmers infrastruktur


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