We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively, each being best possible in its own setting.

We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If $G\sim G(n,p)$ and $p\displaystyle \geq\frac{100\log n}{n}$ then the expected running time of CertifyHAM is $O\left(\displaystyle \frac{n}{p}\right)$ which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and Krivelevich, who proved analogous results for p being constant, $p\geq 12n^{-1/3}$ and $p\geq 70n^{-1/2}$ respectively.

We study the Hamiltonicity of the following model of a random graph. Suppose that we partition $[n]$ into $V_1,V_2,\ldots,V_k$ and add edge $\{x,y\}$ to our graph with probability $p$ if there exists $i$ such that $x,y\in V_i$. Otherwise, we add the edge with probability $q$. We denote this model by ${\mathcal G}({\bf n}, p,q)$ and give tight results for Hamiltonicity, including a critical window analysis, under various conditions.

Let $Ω_q=Ω_q(H)$ denote the set of proper $[q]$-colorings of the hypergraph $H$. Let $Γ_q$ be the graph with vertex set $Ω_q$ and an edge ${σ,τ\}$ where $σ,τ$ are colorings iff $h(σ,τ)=1$. Here $h(σ,τ)$ is the Hamming distance $|\{v\in V(H):σ(v)\neqτ(v)\}|$. We show that if $H=H_{n,m;k},\,k\geq 2$, the random $k$-uniform hypergraph with $V=[n]$ and $m=dn/k$ then w.h.p. $Γ_q$ is connected if $d$ is sufficiently large and $q\gtrsim (d/\log d)^{1/(k-1)}$.

We introduce a natural generalization of the Erdős-Rényi random graph model in which random instances of a fixed motif are added independently. The binomial random motif graph $G(H,n,p)$ is the random (multi)graph obtained by adding an instance of a fixed graph $H$ on each of the copies of $H$ in the complete graph on $n$ vertices, independently with probability $p$. We establish that every monotone property has a threshold in this model, and determine the thresholds for connectivity, Hamiltonicity, the existence of a perfect matching, and subgraph appearance. Moreover, in the first three cases we give the analogous hitting time results; with high probability, the first graph in the random motif graph process that has minimum degree one (or two) is connected and contains a perfect matching (or Hamiltonian respectively).

We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string $\Pi$ over a set of colors $\{1,2,\ldots,r\}$, we say that a Hamilton cycle is $\Pi$-colored if the pattern repeats at intervals of length $|\Pi|$ as we go around the cycle. We prove a hitting time result for the existence of such a cycle. We also prove a hitting time result for the related notion of $\Pi$-connected.

In this paper, we study the connectivity properties of the random subgraph of the n-cube generated by the k-out model and denoted by Q^n(k). Let k be an integer, 1 łeq k łeq n-1. We let Q^n(k) be the graph that is generated by independently including for every v \in V(Q^n) a set of k distinct edges chosen uniformly from all the \binomnk sets of distinct edges that are incident to v. We study the connectivity properties of Q^n(k) as k varies. We show that without high probability (w.h.p.), Q^n(1) does not contain a giant component i.e., a component that spans Ømega(2^n) vertices. Thereafter, we show that such a component emerges when k=2. In addition, the giant component spans all but o(2^n) vertices, and hence it is unique. We then establish the connectivity threshold found at k_0=łog_2 n-2łog_2łog_2 n. The threshold is sharp in the sense that Q^n(łfloor k_0\rfloor ) is disconnected but Q^n(łceil k_0\rceil+1) is connected w.h.p. Furthermore, we show that w.h.p., Q^n(k) is k-connected for every k \geq łceil k_0\rceil+1.

Consider a directed analogue of the random graph process on $n$ vertices, where the $n(n-1)$ edges are ordered uniformly at random and revealed one at a time. It is known that with high probability (w.h.p.) the first digraph in this process with both in-degree and out-degree $\geq q$ has a $q$-edge-coloring with a Hamilton cycle in each color. We show that this coloring can be constructed online, where each edge must be irrevocably colored as soon as it appears. In a similar fashion, for the undirected random graph process, we present an online $n$-edge-coloring algorithm which yields w.h.p. $q$ disjoint rainbow Hamilton cycles in the first graph containing $q$ disjoint Hamilton cycles.