Hamiltonicity threshold conjecture for randomly perturbed directed graphs

About 2 years old · traced to

Let DD be a directed graph on nn vertices with minimum semidegree dd, and let D(n,p)D(n,p) be the binomial random digraph obtained by adding each possible directed edge independently with probability pp. Let d=n/2−ηd=n/2-\eta, where 1/2≤η=η(n)=o(n)1/2\leq\eta=\eta(n)=o(n).

Directed Hamiltonicity threshold conjecture. The dd-threshold for Hamiltonicity in randomly perturbed directed graphs is η/n2\eta/n^2.

This extends the paper's threshold questions from graphs to directed graphs in the critical regime below semidegree n/2n/2. The extension of the corresponding graph theorem to digraphs is stated to remain open.

References

Primary source

Alberto Espuny Díaz and Richarlotte Valérà Razafindravola, “How many random edges make an almost-Dirac graph Hamiltonian?”, arXiv:2410.14447 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.