Hamiltonicity threshold conjecture for randomly perturbed directed graphs

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.

Sources & referencesView supporting material

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.