Posts tagged: netafræði

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

Benedikt Magnússon, október 6, 2016


Arnbjörg Soffía Árnadóttir
Titill: Grúpuverkanir á óendanleg stefnd net og hlutbrautafallið

Staðsetning: Naustið, Endurmenntun.
Tímasetning: Fimmtudagur 6. október 2016, klukkan 16:00.


Við notum grúpuverkanir til þess að skoða óendanleg stefnd net. Við byrjum á því að skilgreina grúpumótun sem við köllum hlutbrautafallið. Við notum svo þessa mótun til þess að skoða ýmsa eiginleika óendanlegra stefndra neta, þ.á.m. myndir netamótana, háörvavegagegnvirkni, Cayley-Abels net og vöxt neta.

Leiðbeinendur: Rögnvaldur G. Möller og Jón Ingólfur Magnússon, báðir prófessorar við Raunvísindadeild Háskóla Íslands.
Prófdómari: Peter M. Neumann, emerítus við The Queen’s College, Oxford University.


Anthony Bonato (30/06/16)

Sigurður Örn Stefánsson, júní 27, 2016

Málstofa í stærðfræði

Fyrirlesari: Anthony Bonato
Titill: Conjectures on Cops and Robbers Games on Graphs

Staðsetning: TG-227 (Tæknigarður, 2. hæð)
Tími: Fimmtudagur 30. júní kl. 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)

Málstofa í stærðfræði

Fyrirlesari: François David
Titill: Planar maps, circle patterns and 2D gravity

Staðsetning: V-157, VRII.
Tími: Föstudagur 11. mars kl. 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, október 12, 2015

Málstofa í stærðfræði

Fyrirlesari: Páll Melsted
Titill: Space Utilization of Cuckoo Hashtables

Staðsetning: V-157, VRII.
Tími: Föstudagur 23. október, klukkan 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

Málstofa í stærðfræði

Fyrirlesari: Matthias Hamann
Titill: Accessible groups and graphs

Staðsetning: V-157, VRII.
Tími: Föstudagur 2. október, klukkan 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

Málstofa í stærðfræði

Fyrirlesari: Florian Lehner
Titill: Cops, robbers, and infinite graphs

Staðsetning: V-157, VRII.
Tími: Föstudagur 11. september, klukkan 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, júní 1, 2015

Málstofa í stærðfræði

Fyrirlesarar: Bjarni Jens Kristinsson, Háskóla Íslands, og Henning Úlfarsson, Háskólanum í Reykjavík
Titill: Occurrence graphs of patterns in permutations

Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 4. júní, klukkan 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, maí 15, 2015

Málstofa í stærðfræði

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

Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 21. maí, klukkan 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, maí 4, 2015

Málstofa í stærðfræði

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

Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 7. maí, klukkan 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, nóvember 13, 2014

Málstofa í stærðfræði

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

Staðsetning: V-157, VRII
Tími: Mánudagur 17. nóvember, frá 15:00 til 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.