# Jan Dreier

I am a PhD candiate at the Theory Group. I am interested in parameterized complexity, graph theory and logic.

## Contact

 Email: dreier@cs.rwth-aachen.de Office: Room 4105b

## Talks

• My talk about efficient model-checking for first-order logic on preferential attachment graphs at TACO Day 2018.

## Publications

• #### The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness

Preprint • Jan Dreier, Philipp Kuinke, Peter Rossmanith • 2018

Preferential attachment graphs are random graphs designed to mimic properties of typical real world networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We use improved concentration bounds for vertex degrees to show that preferential attachment graphs contain asymptotically almost surely (a.a.s.) a one-subdivided clique of size at least (log n)^1/4. Therefore, preferential attachment graphs are a.a.s somewhere-dense. This implies that algorithmic techniques developed for sparse graphs are not directly applicable to them. The concentration bounds state: Assuming that the exact degree d of a fixed vertex (or set of vertices) at some early time t of the random process is known, the probability distribution of d is sharply concentrated as the random process evolves if and only if d is large at time t.

• #### Local Structure Theorems for Erdős-Rényi Graphs and Their Algorithmic Applications

SOFSEM • Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith • 2018

We analyze local properties of sparse Erdős–Rényi graphs, where d(n)/n is the edge probability. In particular we study the behavior of very short paths. For d(n)=o(1) we show that G(n,d(n)/n) has asymptotically almost surely (a.a.s.) bounded local treewidth and therefore is a.a.s. nowhere dense. We also discover a new and simpler proof that G(n,d/n) has a.a.s. bounded expansion for constant d. The local structure of sparse Erdős–Rényi graphs is very special, which implies efficient algorithms for subgraph isomorphism, in particular for finding subgraphs with small diameter.