Jan. 26, 3:30pm, Wean 8220

Tony Johansson, CMU

Random graphs and algorithms (thesis defense)

Tony Johansson, CMU

Random graphs and algorithms (thesis defense)

Abstract:

In this thesis defence I will cover five related topics, summarizing the research I have been conducting during my graduate program. Four topics will be presented in short before going deeply into the final topic.

Firstly, connectivity results in *k*-out random subgraphs of general graphs with large minimum degree will be presented. In particular, conditions under which a random *k*-out subgraph of a graph *G* will contain a Hamilton cycle with high probability will be presented. Secondly, the topic of online
bipartite matching will be presented, focusing on proving that the cucko hashing algorithm with random walk insertion has constant expected insertion time.

Two separate random optimization problems will be presented. We will show that the random graphs *G _{n, p}* and

The majority of the talk will be concerned with a preferential attachment graph with online deletion of oldest edges. We fix parameters *m*≥ *1* and *1*/*2* < *p* < *1*. Given a graph *G _{t}* we form

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.