General graph conjecture for social connectivity time
General graph conjecture for social connectivity time
Let be a connected graph with vertices and average degree . Let denote its social connectivity time. General graph conjecture. There exists a universal constant such that, with probability at least ,
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
Sign in to submit a solution.
No solutions have been posted yet.