Random totally simple graph conjecture

Less than 1 year old · traced to

Fix an integer k≥2k\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 simple∣SCC)→n→∞1.\Pr(\text{$G$ is totally simple}\mid \mathrm{SCC})\xrightarrow[n\to\infty]{}1.

Moreover, for fixed nn, the function

k⟼Pr⁡(G is totally simple∣SCC)k\longmapsto\Pr(\text{$G$ is totally simple}\mid\mathrm{SCC})

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

Pr⁡(G is totally simple∣SCC)=1−exp⁡(−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.

References

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.