SPEAKER: Prasad Chebolu
TIME: Thursday 4:30-5:30 pm, November 16th, 2006
PLACE: PPB 300
TITLE: Thesis Proposal: Topics in Random Graphs
Thesis Committee: Alan Frieze(chair), Anupam Gupta, R Ravi
Abstract: We study the hamiltonicity property of a new class of random graphs- random lifts in both undirected and directed graphs. In the undirected case, we show that for sufficiently large h>0 random lifts of K_h and K_{h,h} are Hamiltonian. In the case of directed graphs, we obtain a similar result for the complete directed graph.
We also study the average performance of the greedy matching algorithm in sparse random hypergraphs. We are currently working on developing a matching algorithm for sparse random graphs which runs in time O(n) with high probability.
As future work, we would like to obtain conditions under which strong connectivity holds in random lifts of digraphs.
This proposal includes joint work with Kelley Burgin, Colin Cooper, Alan Frieze and Pall Melsted.
