The threshold-exponent conjecture for K_d-completion

Consider the KdK_d-completion dynamics on [n][n], in which copies of KdK_d missing one edge are iteratively completed, with initial graph G0G_0 having edges iji\leftrightarrow j whenever ijd2|i-j|\le d-2. Let pcp_c denote the critical probability for saturation. KdK_d-completion threshold-exponent conjecture. There exists a power γ=γ(d)>0\gamma=\gamma(d)>0 such that, for large nn, pcp_c lies between two constant multiples of

(loglogn)γ(logn)1/(d1).(\log\log n)^{\gamma}(\log n)^{-1/(d-1)}.

This predicts the threshold scale for nucleation and saturation in the KdK_d-completion dynamics; the paper presents the claim as an unresolved conjecture motivated by simulations and known results for the unpolluted process.

Sources & referencesView supporting material

Primary source

Janko Gravner and Brett Kolesnik, “Transitive closure in a polluted environment”, arXiv:1910.01800 (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.