Random totally simple graph conjecture

Fix an integer k2k\geq 2. Let GG be a uniformly random kk-out graph on nn vertices, and let SCC\mathrm{SCC} be the event that GG is strongly connected. A graph is totally simple if it has no nontrivial graph congruences.

Random totally simple graph conjecture. One has

Pr(G is totally simpleSCC)n1.\Pr(\text{$G$ is totally simple}\mid \mathrm{SCC})\xrightarrow[n\to\infty]{}1.

Moreover, for fixed nn, the function

kPr(G is totally simpleSCC)k\longmapsto\Pr(\text{$G$ is totally simple}\mid\mathrm{SCC})

is nondecreasing. More quantitatively, there exist constants ck>0c_k>0 and βkR\beta_k\in\mathbb R such that

Pr(G is totally simpleSCC)=1exp(ckn+βk)+o(1)(n),\Pr(\text{$G$ is totally simple}\mid\mathrm{SCC})=1-\exp(-c_kn+\beta_k)+o(1)\qquad(n\to\infty),

with ckc_k increasing as kk 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

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.