Title: Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application,
Abstract: We analyze some local properties of sparse Erdos-Renyi graphs, where $d(n)/n$
is the edge probability. In particular we study the behavior of very short
paths. For $d(n)=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 Erdos-Renyi Gaphs is
very special: The $r$-neighborhood of a vertex is a tree with some additional
edges, where the probability that there are $m$ additional edges decreases
with~$m$. This implies efficient algorithms for subgraph isomorphism, in
particular for finding subgraphs with small diameter. Finally we note that
experiments suggest that preferential attachment graphs might have similar
properties after deleting a small number of vertices.