Sparse Random Graphs: Methods, Structure, and Heuristics

This dissertation is an algorithmic study of sparse random graphs which are parametrized by the distribution of vertex degrees. Our contributions include: a formula for the diameter of various sparse random graphs, including the Erdős-Renyi random graphs Gn,m and Gn,p and certain power-law graphs; a heuristic for the k-orientability problem, which performs optimally for certain classes of random graphs, again including the Erdős-Renyi models Gn,m and Gn,p; an improved lower bound for the independence ratio of random 3-regular graphs. In addition to these structural results, we also develop a technique for reasoning abstractly about random graphs by representing discrete structures topologically.