Posts tagged: graph theory

Arnbjörg Soffía Árnadóttir (06/10/16)

Benedikt Magnússon, October 6, 2016


Arnbjörg Soffía Árnadóttir
Title: Group actions on infinite digraphs and the suborbit function

Location: Naustið, Endurmenntun.
Time: Thursday October 6. 2016 at 16:00.


We study infinite directed graphs, using group actions. We start by defining a group homomorphism called the suborbit function. Then we use this homomorphism to investigate various properties of infinite digraphs, including homomorphic images, highly arc transitive digraphs, Cayley-Abels digraphs and the growth of digraphs.

Advisors: Professor Rögnvaldur G. Möller and professor Jón Ingólfur Magnússon at Science Institute, University of Iceland.
Examiner: Professor emeritus Peter M. Neumann The Queen’s College, Oxford University.

Anthony Bonato (30/06/16)

Math Colloquium

Speaker: Anthony Bonato
Title: Conjectures on Cops and Robbers Games on Graphs

Location: TG-227 (Tæknigarður, 2nd floor)
Time: Thursday, June 30 at 13:20.


The game of Cops and Robbers gives rise to a rich set of conjectures, mainly associated with the cop number of a graph. Arguably the most important such conjecture is Meyniel’s, which posits a \(O(n^{1/2})\) upper bound on the cop number of a connected graph of order n. We discuss the state-of-the-art on Meyniel’s conjecture, and explore other conjectures on cop number ranging from topics within computational, probabilistic, and topological graph theory.

François David (11/03/16)

Math Colloquium

Speaker: François David
Title: Planar maps, circle patterns and 2D gravity

Location: V-157, VRII.
Time: Friday, March 11 at 13:20.


I present a model of random planar triangulations (planar maps) based on circle patterns and discuss its properties. It exemplifies the relations between discrete random geometries in the plane, conformally invariant point processes and two dimensional quantum gravity (Liouville theory and topological gravity).

Páll Melsted (23/10/15)

Sigurður Örn Stefánsson, October 12, 2015

Math Colloquium

Speaker: Páll Melsted
Title: Space Utilization of Cuckoo Hashtables

Location: V-157, VRII.
Time: Friday, October 23, at 15:00-16:00.


We study the space requirements for Cuckoo Hashing. This can be reduced to
the following question in Random Graphs.

We are given two disjoint sets L,R with |L|=n=alpha*m and |R|=m. We construct a random graph G by allowing each x in L to choose d random neighbours in R. The problem is to find m(G), the size of the largest matching in G.

From the point of view of Cuckoo Hashing, a key question is to locate the threshold for when m(G)=n with high probability, since if m(G) < n it is impossible to store all items. We answer this question exactly for all values of d.

Matthias Hamann (02/10/15)

Sigurður Örn Stefánsson, September 28, 2015

Math Colloquium

Speaker: Matthias Hamann
Title: Accessible groups and graphs

Location: V-157, VRII.
Time: Friday, October 2, at 15:00-16:00.


The talk falls into two parts. First, we give an overview of the group theoretical concept of accessibility and the main results in this area.
In the second part, we define the graph theoretical notion of accessibility. After a brief discussion of the connection of these two kinds of accessibility, we reinterpret the mentioned group theoretic theorems graph theoretically. This leads to many new questions some of which are solved and others are widely open.

Florian Lehner (11/09/15)

Sigurður Örn Stefánsson, September 7, 2015

Math Colloquium

Speaker: Florian Lehner
Title: Cops, robbers, and infinite graphs

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


Pursuit-evasion based searching, also known as the game of cops and robbers is a game on a graph between two players, $C$ (the cop) and $R$ (the robber). The rules are as follows: In the first round both $C$ and $R$ choose a starting vertex, in each consecutive round they are allowed to move to a neighboring vertex. The cop wins the game, if after some finite number of steps $C$ and $R$ occupy the same vertex, otherwise the robber wins.

A basic question related to this game is to characterize the class of graphs for which the cop has a winning strategy. For finite graphs it has been shown by Nowakowski and Winkler that these are exactly the constructible graphs.

For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they believed the same to be true. We disprove this conjecture and explore further modifications which may lead to an extension of the result of Nowakowski and Winkler.

Bjarni Jens Kristinsson and Henning Úlfarsson (04/06/15)

Benedikt Magnússon, June 1, 2015

Math Colloquium

Speaker: Bjarni Jens Kristinsson, University of Iceland, and Henning Úlfarsson, Reykjavik University
Title: Occurrence graphs of patterns in permutations

Location: Naustið, Endurmenntun (here)
Time: Thursday, June 04, at 15:00-16:00.


This paper is based on a generalisation of the idea behind the proof of the Simultaneous Shading Lemma by Claesson et al. (2014). We define the occurrence graph \(G_p(\pi)\) of a pattern \(p\) in a permutation \(\pi\) as the graph with the occurrences of \(p\) in \(\pi\) as vertices and edges between the vertices if the occurrences differ by exactly one element. We study the general properties of the occurrence graphs and some interesting extreme cases. The main theorem in this paper is that every hereditary property of graphs produces a permutation class.

Rögnvaldur Möller (21/05/15)

Benedikt Magnússon, May 15, 2015

Math Colloquium

Speaker: Rögnvaldur Möller
Title: Infinite cubic vertex-transitive graphs

Location: Naustið, Endurmenntun (here)
Time: Thursday, May 21, at 15:00-16:00.


Tutte’s two papers from 1947 and 1959 on cubic graphs were the starting point of the in-depth study of the interplay between the structure of a group and the structure of a graph that the group acts on. In this talk I will describe applications of Tutte’s ideas where it is assumed that the graph is infinite and the stabilizers of vertices are infinite.

Thomas Vallier (07/05/15)

Benedikt Magnússon, May 4, 2015

Math Colloquium

Speaker: Thomas Vallier, University of Iceland
Title: Majority bootstrap percolation on \(G(n,p)\).

Location: Naustið, Endurmenntun (here)
Time: Thursday, May 7, at 15:00-16:00.


Majority bootstrap percolation is a process of spread of “activation” on a given graph with a given number of initially active nodes \(A(0)\)chosen uniformly at random. At each step those vertices which have more active neighbours than inactive neighbours become active as well.

Sigurður Örn Stefánsson and I consider the process on the random graph \(G(n,p)\)which consists of \(n\)vertices where each pair of vertices is present with probability \(p\)independently of the others.

The process is more involved than the classical bootstrap percolation for which a certain number of active neighbours is required for a vertex to become active. Moreover, the fact that the degree of a vertex, that is, it’s number of neighbours, is random makes the study more difficult than on structures with deterministic neighbourhood.

We study the size \(A^*\)of the final active set depending on the size of the set of initially active vertices for all ranges of \(p=p(n)\). We show that the model exhibits different behaviours for different ranges of \(p\).

I will let you guess the threshold \(A_c(p(n))\) for the process to “percolate” (that means that the activation spreads to almost all the graph) for the following ranges:

  • \(p=o\left(\frac{1}{n}\right)\)
  • \(p \gg \frac{1}{n}\)
  • \(p = \frac{c}{n}\)

and will eventually give you the answer.

Jakob Björnberg (17/11/14)

Benedikt Magnússon, November 13, 2014

Math Colloquium

Speaker: Jakob Björnberg, Chalmers Tekniska Högskola, Göteborg
Title: Percolation in random quadrangulations of the half-plane

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


The topic of random planar quadrangulations (and, more generally, random planar maps) is of interest to probabilists, combinatorialists and physicists alike. Recent years have seen considerable progress on understanding large random planar maps themselves, and the next big challenge is to understand maps “with matter”; that is, to study models from statistical physics on large random planar maps. In this talk we consider such a model, specifically site percolation on uniform quadrangulations of the half-plane. The talk is based on ongoing work together with Sigurdur Stefansson (Reykjavik) where we use a “spatial Markovian property” of the quadrangulations (first described by O. Angel) to study the percolation phase transition. We will describe this Markovian property, see how Angel (et al) used it in the case of triangulations, and discuss results and challenges for the case of quadrangulations.