Posts tagged: graph theory

Sigurður Örn Stefánsson (27/10/14)

Benedikt Magnússon, October 23, 2014

Math Colloquium

Speaker: Sigurður Örn Stefánsson, University of Iceland
Title: Convergence of random planar maps to the Brownian tree

Location: V-157, VRII
Time: Monday, October 27 at 15:15-16:15.

Abstract:

Random planar maps are defined by assigning non-negative weights to each face of a planar map and the weight of a face depends only on its degree. I will explain the Bouttier-Di Francesco-Guitter bijection between the planar maps and a class of labelled trees called mobiles. By throwing away labels one can, via another bijection, relate the mobiles to the model of so-called simply generated trees which are understood in detail. For certain choices of weights a unique large face, having degree proportional to the total number of edges in the maps, appears with high probability when the maps are large. This corresponds to a recently studied phenomenon of condensation in simply generated trees where a vertex having degree proportional to the size of the trees appears. In this case the planar maps, with a properly rescaled graph metric, are shown to converge in distribution towards Aldous’ Brownian tree in the Gromov-Hausdorff topology.

Sara Sabrina Zemljic (20/10/14)

Benedikt Magnússon, October 16, 2014

Math Colloquium

Speaker: Sara Sabrina Zemljic, University of Iceland
Title: Sierpiński graphs, continued

Location: V-157, VRII
Time: Monday, October 20 at 15:00-16:00.

Abstract:

Sierpiński graphs \(S_p^n\) form an extensively studied family of graphs of fractal nature applicable in topology, mathematics of the Tower of Hanoi, computer science, and elsewhere. In the talk we will take a closer look at these graphs and go through some of their basic properties.

Sara Sabrina Zemljic (06/10/14)

Benedikt Magnússon, October 2, 2014

Math Colloquium

Speaker: Sara Sabrina Zemljic, University of Iceland
Title: Sierpiński graphs

Location: V-157, VRII
Time: Monday, October 6 at 15:00-16:00.

Abstract:

Sierpiński graphs \(S_p^n\) form an extensively studied family of graphs of fractal nature applicable in topology, mathematics of the Tower of Hanoi, computer science, and elsewhere. In the talk we will take a closer look at these graphs and go through some of their basic properties.

Thomas Vallier (15/09/14)

Benedikt Magnússon, September 11, 2014

Math Colloquium

Speaker: Thomas Vallier, University of Iceland
Title: Bootstrap percolation on the random graph \(G_{n,p}\)

Location: V-157, VRII
Time: Monday September 15, at 15:00-16:00.

Abstract:

Bootstrap percolation on the random graph \(G_{n,p}\) is a process of spread of “activation” on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least \(r ≥ 2\) active neighbours become active as well.

We consider the n vertices with global connections inherited from the structure of the graph \(G_{n,p}\), meaning that any two vertices share an edge with probability \(p\) independently of the others.

The presentation is based on the article ”Bootstrap percolation on the random graph \(G_{n,p}\)” by Janson, Luczak, Turova and Vallier.

Among other results, they study the size \(A^*\) of the final active set depending on the number of vertices active at the origin as a function of n (the number of vertices) and \(p = p(n)\) (the probability of connections) which is written \(a_0(n, p) = a_0\). The model exhibits a sharp phase transition: depending on the parameters of the model the final size of activation with a high probability is either \(n − o(n)\) or it is \(o(n)\).

I will give a pictorial introduction to the model and explain briefly the approach of the authors to derive the threshold for bootstrap percolation on \(G_{n,p}\).