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