Feasibility of partial alignment in the Erdős–Rényi model above the threshold
Statement
Let be the number of graphs, let be the underlying permutation tuple, and let denote their overlap. In the Erdős–Rényi model, with parameters and , assume
Feasibility conjecture. Partial alignment is feasible: there exists an estimator and some such that, with high probability,
This statement complements the preceding theorem asserting intractability below the threshold . The source presents the above-threshold claim without a proof or an explicit resolution, so its status remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.