Given a graph $G$ and $k\le \delta(G)$, the $k$-out model, $\mathcal{G}\_{k-out}(G)$ is a distribution on subgraphs $H$ of $G$ determined by the following: for $v\in G$, we choose a uniformly random subset $S\_v\subset N(v)$ of size $k$, we conclude by taking $H$ to have the edges $\{(v,u):v \in G, u \in S\_v\}$.


Bohman and Frieze showed that whp, $\mathcal{G}\_{3-out}(K\_n)$ contains a hamiltonian cycle. My intuition believes that the situation should change if we instead look for the square of a hamiltonian cycle (for an $n$-vertex graph $G$, we say it contains the square of a hamiltonian cycle if there are distinct $v\_1,...,v\_n \in G$ such that $(v\_i,v\_{i+1}),(v\_i,v\_{i+2})\in E(G)$ for all $i$ (here addition is done modulo $n$)).


More precisely, I believe that for any finite $k$, we have that asymptotically almost surely $\mathcal{G}\_{k-out}(K\_n)$ does not contain the square of a hamiltonian cycle. Is this correct?



$k$-out model containing the square of a hamiltonian cycle
Your statement is correct, because there are too few triangles in $\mathcal G\_{k-out}(K\_n)$.


For three vertices $a,b,c \in \mathcal G\_{k-out}(K\_n)$ to form a triangle, the edges $ab$, $bc$ and $ca$ should all be present, and the probability is $O(n^{-3})$ after $k$ is fixed. Thus the expected number of triangles is $O(1)$ for fixed $k$. Because a square of hamiltonian cycle contains $n$ triangles (for $n\geq7$), the probability for a square of hamiltonian cycle to appear is $O(1/n)$ by the Markov inequality.


