| 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. |
