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.
References
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
No solutions have been posted yet.