A note on spanning K_r-cycles in random graphs

1.   Introduction

In a seminal paper, Johansson, Kahn and Vu ^[6] solved the long standing open question of determining the threshold for the existence of $H$-factors in random graphs and hypergraphs. For some questions, the proof for hypergraphs turns out to be somewhat simpler than that of the related question in graphs. More precisely, the proof of the existence of a perfect matching in a random $r$-uniform hypergraph is simpler than the proof of the existence of a $K_r$-factor in $G_{n, p}$. Recently Riordan ^[7] showed that one can avoid the more complicated proofs. He does this by proving a coupling between graphs and hypergraphs that enables one to infer graph factor thresholds from hypergraph matching thresholds. The aim of this short note is to show how to use this coupling to prove thresholds for some other spanning subetaaphs.

We are given a graph $G$ with $n$ vertices and an integer $r\geq 3$ where $n = (r-1)m$, $m$ integer. A $K_r$-cycle is a sequence $H_1, H_2, \ldots, H_m$ of copies of $K_r$ where (ⅰ) $V(H_i)\cap V(H_{i+1}) = \left\{{v_i}\right\}, i = 1, 2 \ldots, m$ ($v_{m+1} = v_1$ here) and (ⅱ) $H_i$ and $H_j$ are vertex disjoint for $i\neq j$.

We will prove the following theorem:

Theorem 1. $p = n^{-2/r}\log^{1/\binom{r}{2}}n$ is a threshold for $G_{n, p}$ to contain a spanning $K_r$-cycle.

2.   Proof of Theorem 1

For the proof, we need two results: the first will be Theorem 1 of Riordan ^[7] combined with Theorem 2 of Heckel ^[5].

Theorem 2. Let $r\geq 3$ be given. There is a positive constant ${\epsilon}$ such that if $p\leq n^{-2/r+{\epsilon}}$ then, for some ${\pi}\approx p^{\binom{r}{2}}$, we may couple $G = G_{n, p}$ and the random $r$-uniform hypergraph $H = H_{n, {\pi}; r}$ such that w.h.p. to every edge $e$ of $H$ there is a corresponding copy of $K_r$ in $G$ with $V(K_r) = e$.

We will also need the following theorem from Dudek, Frieze, Loh and Speiss ^[2], which removed some divisibility constraints from ^[1,4]. A loose Hamilton cycle $C$ in an $r$-uniform hypergraph $H = (V, \mathcal{E})$ of order $n$ is a collection of edges of $H$ such that for some cyclic ordering of $V$, every edge consists of $r$ consecutive vertices, and for every pair of consecutive edges $E_{i-1}, E_i$ in $C$ (in the natural ordering of the edges), we have $|E_{i-1}\cap E_i| = 1$.

Theorem 3. Suppose $k\geq 3$. If ${\pi} = {\omega} n^{1-r} \log n$ for ${\omega} = {\omega}(n)\to\infty$, then

Proof of Theorem 1

First suppose that $p = {\omega} n^{-2/r}\log^{1/\binom{r}{2}}n$. We couple $G_{n, p}$ with the hypergraph $H_{n, {\pi}; r}$ as promised by Theorem 2. Because $p^{\binom{r}{2}} = ({\omega} n^{-2/r}\log^{1/\binom{r}{2}}n)^{\binom{r}{2}} = {\omega}^{\binom{r}{2}}n^{1-r}\log n$ we see from Theorem 3 that w.h.p. $H_{n, {\pi}; r}$ contains a loose Hamilton cycle. When lifted back to $G_{n, p}$ via Theorem 2 we get the promised $K_r$-cycle.

If $p = {\omega}^{-1}n^{-2/r}\log^{1/\binom{r}{2}}n$ then Lemma 1.4 of ^[6] implies that w.h.p. there will be vertices that are not in a copy of $K_r$.

This completes the proof of Theorem 1.

3.   Discussion and open problems

We first note that we can replace $K_r$ by any strictly 1-balanced graph $F$ and then apply Theorem 15 of ^[7] and obtain a spanning subetaaph made up of a sequence of edge disjoint copies of $F$, where adjacent copies in the sequence share exactly one common vertex. More precisely, for a graph $F$ we let $d_1(F) = \frac{|E(F)|}{|V(F)|-1}$. A graph is strictly 1-balanced if $d_1(F) > d_1(F')$ for all subetaaphs $F'\subseteq F$ with at least two vertices. Theorem 15 amends Theorem 2 by having the requirement that $p\leq n^{-1/d_1+{\epsilon}}$ and letting ${\pi} = ap^{|E(F)|}$ for some constant $a > 0$. Note that $|E(F)| = \binom{r}{2}$ $d_1(K_r) = r/2$ and so Theorem 1 is just a special case, other than the knowledge that we can take $a = 1$. We call the constructions that arise $F$-cycles.

There is a weakness in the result. Consider the diagram below:

We cannot use the above argument to show that the threshold for an $n$-vertex copy of the above example has a threshold at $p = n^{-3/4+o(1)}$. The reason being that we have no control over the positioning of the connecting vertices i.e. we cannot prevent something like the following being part of the $F$-cycle:

It is therefore an open question as to the threshold for the existence of a spanning $C_4$-cycle.

The proof also breaks if our adjacent copies share two or more vertices, as in the diagrams below:

One can check that the probability an edge occurs in $H$ is not sufficient to imply the existence of a Hamilton cycle of the requisite type as in ^[2]. For the first example, the expected number of copies of a spanning $C_4$-cycle in $G_{n, p}$ is given by $n!p^{3n/2}$ and so we should take $p\approx n^{-2/3}$. But then ${\pi}$ will be chosen as $\approx n^{-8/3}$ and this is below the threshold of ${\omega} n^{-2}$ for a Hamilton cycle of the required type, see Theorem 3(ⅲ) of ^[1]. We have a similar experience with the second example, with $p\approx n^{-1/2}$ and ${\pi}\approx n^{-5/2}$.

On the other hand, a recent result of Frankston, Kahn, Narayanan and Park ^[3] enables us to argue that the suggested thresholds are no worse than $\log n$ from the correct values.

Acknowledgments

The author thanks Research supported in part by NSF grant DMS1661063.

Conflict of interest

The author declares no conflicts of interest in this paper.