Random totally simple graph conjecture
Random totally simple graph conjecture
Fix an integer . Let be a uniformly random -out graph on vertices, and let be the event that is strongly connected. A graph is totally simple if it has no nontrivial graph congruences.
Random totally simple graph conjecture. One has
Moreover, for fixed , the function
is nondecreasing. More quantitatively, there exist constants and such that
with increasing as increases.
The conjecture proposes that, after conditioning on strong connectivity, random fixed-out-degree graphs are typically totally simple, and it further predicts monotonicity and an exponential rate. The source provides no resolution status.
Sources & referencesView supporting material
Primary source
Daniele D'Angeli and Emanuele Rodaro, “On totally synchronizing graphs”, arXiv:2607.17335 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.