Upcoming Talks

Vortrag im Seminar für Kombinatorik und Optimierung

Title: Deletion of oldest edges in a preferential attachment graph
Speaker: Tony Johansson (Carnegie Mellon University)
Date: Dienstag 7.3.2017
Room: Seminarraum AE06, Steyrergasse 30, Erdgeschoss
Abstract:

We consider a variation on the Barab\'asi-Albert random graph process with fixed parameters $m\in \mathbb{N}$ and $1/2 < p < 1$. With probability $p$ a vertex is added along with $m$ edges, randomly chosen proportional to vertex degrees. With probability $1 - p$, the oldest vertex still holding its original $m$ edges loses those edges. It is shown that the degree of any vertex either is zero or follows a geometric distribution. If $p$ is above a certain threshold, this leads to a power law for the degree sequence, while a smaller $p$ gives exponential tails.
It is also shown that the graph contains a unique giant component with high probability if and only if $m \ge 2$.

Vortrag im Seminar für Kombinatorik und Optimierung

Title: On hyperbolicity of small-world and tree-like random graphs
Speaker: Wenjie Fang (ENS de Lyon)
Date: Freitag 3.3.2017, 14:15
Room: Seminarraum AE06, Steyrergasse 30, Erdgeschoss
Abstract:

Complex networks are real-world large graphs that share many intriguing properties. Recent studies suggest that there may be some hidden hyperbolic geometry behind some complex networks that can explain some of their remarkable properties. One of these properties is navigability, which is a highly desirable phenomenon which means that we can navigate in the graph using only local information. To measure how ``hyperbolic'' a graph is, we use Gromov's notion of $\delta$-hyperbolicity. A graph with a good hyperbolicity can be seen as a ``soften'' version of trees. In this talk, we will explore the connection between navigability and hyperbolicity of complex networks by looking at several network models, including Kleinberg small-world random graphs and a new model called ``ringed trees''. We found that there seems to be a discrepancy between navigability and hyperbolicity, which may be related to noises in random graph models.

This is a joint work with Wei Chen, Guangda Hu and Michael W. Mahoney.

Vortrag im Seminar für Kombinatorik und Optimierung

Title: Random Factor Graph Models: The Replica Symmetric Phase
Speaker: Tobias Kapetanopoulos (Goethe-Universität Frankfurt)
Date: Dienstag 21.2.2017, 15:00
Room: Seminarraum AE06, Steyrergasse 30, Erdgeschoss
Abstract:

We proved the absence of extensive long-range correlations throughout the replica symmetric phase}, i.e. below the condensation threshold, for a wide class of random factor graph models, including the p-spin Potts antiferromagnet, random k-NAESAT, random k-XORSAT (for even k), etc. This is done by using Janson’s technique of Small Subgraph Conditioning} to nail down the precise limiting distribution of the free energy in this phase. As an application we show that in the replica symmetric phase the random graph model is statistically indistinguishable from the so-called ``planted model''. This result allows us to verify a general conjecture about the reconstruction phase transition in random factor graph models, which deals with the extent of point-to-set correlations. Additionally, we derive a version of the well-known Kesten-Stigum} bound for general factor graph models.

Joint work with Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari and Mihyun Kang

Vortrag im Seminar für Kombinatorik und Optimierung

Title: Core Forging by Warning Propagation
Speaker: Kathrin Skubch (Goethe-Universität Frankfurt)
Date: Dienstag 21.2.2017, 14:15
Room: Seminarraum AE06, Steyrergasse 30, Erdgeschoss
Abstract:

The $k$-core of a graph is the largest subgraph of minimum degree $k$. It can be determined algorithmically by the peeling process that removes an arbitrary vertex of degree less than $k$ while there is one. In this paper we study the $k$-core of the Erd\H{o}s-R\'enyi random graph $G(n,m)$ for $m=\frac{dn}2$ with some fixed positive constant $d>0$.

We propose a new approach to the $k$-core problem in random graphs. More precisely, we devise a randomised algorithm that produces graphs with a $k$-core of a given order and size.

This algorithm is based on an enhanced ``configuration model'' that explicitly designates which vertices will wind up in the core. As it turns out, the necessary structure to construct such configuration model can be set out by way of Warning Propagation, a message passing scheme that plays an important role in physics work on random constraint satisfaction problems.

This is joint work with Amin Coja-Oghlan, Oliver Cooley and Mihyun Kang.