Cayley-graph disorder–diameter asymptotic conjecture

Less than 1 year old · traced to

Let GG be a finite group, let SS be a generating set, let n=∣G∣n=|G|, and let D(Cay⁡(G,S))\mathfrak{D}(\operatorname{Cay}(G,S)) and A(Cay⁡(G,S))\mathcal{A}(\operatorname{Cay}(G,S)) denote the graph diameter and average graph disorder, respectively. Cayley-graph disorder–diameter asymptotic conjecture. Under appropriate conditions, there is a function ϵ(Cay⁡(G,S))=o(A(Cay⁡(G,S)))\epsilon(\operatorname{Cay}(G,S))=o(\mathcal{A}(\operatorname{Cay}(G,S))), determined by the number of generators in SS of order 22, such that

n D(Cay⁡(G,S))=A(Cay⁡(G,S))−ϵ(Cay⁡(G,S)).n\,\mathfrak{D}(\operatorname{Cay}(G,S))=\mathcal{A}(\operatorname{Cay}(G,S))-\epsilon(\operatorname{Cay}(G,S)).

The conjecture refines the observed inequality nD(Cay⁡(G,S))≤A(Cay⁡(G,S))n\mathfrak{D}(\operatorname{Cay}(G,S))\leq\mathcal{A}(\operatorname{Cay}(G,S)) and proposes that the discrepancy is asymptotically negligible apart from its dependence on involutory generators. The appropriate conditions are not specified in the supplied text.

References

Primary source

Rashid Barket, Enrico Grimaldi, Yacoub Hendi, Edward Hirst, Adam Onus and Harmeet Singh, “Learning the Graphical Nature of Symmetries”, arXiv:2607.12026 (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.