General graph conjecture for social connectivity time

Let GG be a connected graph with nn vertices and average degree dd. Let SC(G)\mathrm{SC}(G) denote its social connectivity time. General graph conjecture. There exists a universal constant C>0C>0 such that, with probability at least 1C/n1-C/n,

SC(G)(logn)2    C(d21{G is non-regular}+d1{G is regular but not vertex-transitive}+1).\frac{\mathrm{SC}(G)}{(\log n)^2}\;\leqslant\; C\left(d^2\mathbf{1}_{\{G\text{ is non-regular}\}}+d\mathbf{1}_{\{G\text{ is regular but not vertex-transitive}\}}+1\right).

This proposes a uniform logarithmic-square upper bound, with the degree dependence distinguishing non-regular, regular non-vertex-transitive, and vertex-transitive graphs.

Sources & referencesView supporting material

Primary source

Itai Benjamini and Jonathan Hermon, “Rapid social connectivity”, arXiv:1608.07621 (2019).

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.