Theta-order modularity conjecture for preferential attachment graphs

Let Gnh=(V,E)G_n^h=(V,E) be a preferential attachment graph, where nn is the number of vertices and hh is the number of edges added per step. Write mod(Gnh)\operatorname{mod}(G_n^h) for its modularity, and let “whp” mean with high probability. The theta-order modularity conjecture. With high probability,

mod(Gnh)=Θ(1/h).\operatorname{mod}(G_n^h)=\Theta(1/\sqrt{h}).

This conjecture would sharpen the known lower bound on modularity to the correct order in hh, substantially improving the available upper bound. The source explicitly states that it remains open.

Sources & referencesView supporting material

Primary source

Katarzyna Rybarczyk and Małgorzata Sulkowska, “Modularity of preferential attachment graphs”, arXiv:2501.06771 (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.