Complete-network maximizer conjecture for homogeneous finite networks

Fix parameters p,qp,q and a positive integer MM, and let

G(p,q,M):={NN has M nodes and satisfies the homogeneity condition in {pj} and {qj}}.{\cal G}(p,q,M):=\{{\cal N}\mid {\cal N}\text{ has }M\text{ nodes and satisfies the homogeneity condition in }\{p_j\}\text{ and }\{q_j\}\}.

For NG(p,q,M){\cal N}\in{\cal G}(p,q,M), write f(t;N)f(t;{\cal N}) for its expected adoption level, and let fcomplete(t;p,q,M)f_{\rm complete}(t;p,q,M) be the adoption level on the homogeneous complete network. Complete-network maximizer conjecture.

supNG(p,q,M)f(t;N)=fcomplete(t;p,q,M).\sup_{{\cal N}\in{\cal G}(p,q,M)} f(t;{\cal N})=f_{\rm complete}(t;p,q,M).

The conjecture asks whether the fastest diffusion among homogeneous networks with a fixed number of nodes is attained by the homogeneous complete network. The supplied text presents it as a new question in the open-problems section, so its resolution is not given here.

Sources & referencesView supporting material

Primary source

Gadi Fibich and Tomer Levin, “Universal Bounds for Spreading on Networks”, arXiv:2312.05450 (2023).

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.