Algorithms on random graphs

The central topic of this thesis is the analysis and design of algorithms on random graphs. First we study the effect that the PageRank algorithm has on the evolution of a random graph, as a model of the web graph. Next, we give a linear time algorithm for finding a maximum cardinality matching in a random graph, and an efficient algorithm for sampling a weak coloring at random in simple hypergraphs. This is followed by an analysis of a random-walk cuckoo hashing scheme, which, although not stated in the problem, depends on analyzing a random walk in a random graph. Finally we consider the expected Vickrey costs for random combinatorial auctions.