Algorithmic and Structural Properties of Random Graphs

All questions considered in this thesis are related to either some class of Random Graphs or to a randomized algorithm or to both. The main property that is studied in Chapters 2,3 & 4 is Hamiltonicity. In Chapter 2 we show that w.h.p. the edges of the random directed graph process can be [q]-colored ([n]-colored respectively) in an online fashion such that once the underlying graph has both minimum in-degree and out-degree  >_q there is a Hamilton cycle in each color
(q edge disjoint rainbow Hamilton cycles respectively).
In Chapter 3 we consider patterned-colored Hamilton cycles. That is a Hamilton cycle where the colors alternate based on some nite patterned as we traverse the cycle. For example if the pattern is b, b, r, then as we traverse the cycle we may see the colors b,b,r,b,b,r,b,b,r,.... We prove a hitting time result for the existence of such a cycle in the randomly colored random graph process as well as a hitting time result for the related notion of patterned connectivity.
In Chapter 4 we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph.
We give upper bounds on the number of colors and edges needed in order for the resultant graph to contain w.h.p. a rainbow Hamilton cycle. We also prove the corresponding
result related to rainbow connectivity. In Chapters 5 & 6 we analyze a version of an algorithm that was proposed Karp
and Sipser for finding perfect matchings in sparse random graphs. We show that it can utilized in order to find perfect matchings in random regular graphs in linear time
in expactation. In Chapters 7 & 8 we study two problems that are related Glauber dynamics. In Chapter 7 we give conditions under which we can utilize the Glauber dynamics in order to sample an almost random coloring of a simple Hypegraph in O(n log n) time. In Chapter 8 we give an upper bound on the number of colors q = q(d) needed such
that w.h.p. the underlying chain, applied to G(n; p = d=n), is ergodic. In Chapter 9 we study the connectivity of the k-out random subgraph of the n-Hypercube, Qⁿ. That is the subgraph that is generated by independently adding
for every vertex of Qⁿ k random edges incident to it. We establish the threshold of existence of a giant component as well as of connectivity. Finally in Chapter 10 we consider a Ramsey property of random d-regular graphs. We determine the exact number of colors needed such that w.h.p. there is a coloring of the edges of a random d-regular graphs where every monochromatic component has sublinear size. We also prove a similar result for the k-out random subgraphs of the complete graph.