Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application

Jan Dreier, Philipp Kuinke, Ba Le Xuan +1

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)}$…