0
$\begingroup$

I am looking for a reference for the following fact. Let $r\geq 3$ be constant, let $G(n,r-2)$ be a random (simple) $(r-2)$-regular graph and let $H(n)$ be an independent random Hamiltonian cycle (on the same vertex set $V=[n]$). Then there exists a positive constant $p_0$ such that, with probability at least $p_0$, the two graphs do not share an edge.

I believe this should follow from contiguity results, something in the spirit of $G(n,r-2)\cup H(n) \approx G(n,r)$. I looked at Wormald [1], which gives several similar results, but I do not see how they imply the particular one above.

Improve this question
$\endgroup$
2
  • $\begingroup$ Does $G(n,r)$ contain a Hamiltonian cycle with a probability bounded away from zero? I would doubt that, and if it is not the case, then the last paragraph does not seem to work. $\endgroup$
    – Ilya Bogdanov
    Commented Aug 30, 2023 at 9:37
  • $\begingroup$ @IlyaBogdanov Yes, with probability approaching $1$ as $n\to\infty$. This was shown in Robinson--Wormald's paper "Almost all regular graphs are Hamiltonian". $\endgroup$
    – Geva Yashfe
    Commented Sep 5, 2023 at 21:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .