Path-graph averaging conjecture without a logarithmic factor

Let PnP_n be the path graph on nn vertices. For a weight vector xx on PnP_n, define

Δ1(t,x)=RPnt(x)x1,\Delta_1(t,x)=\lVert\mathbf{\mathrm{R}}_{P_n}^{t}(x)-\overline{x}\rVert_1,

where x\overline{x} denotes the average-weight vector. Path-graph averaging conjecture. For every c>0c>0, there exists a constant M=M(c)M=M(c) such that, for every weight vector xx of PnP_n,

E[Δ1(Mn3,x)]ecxx2.\mathbb{E}[\Delta_1(Mn^3,x)]\le e^{-c}\lVert x-\overline{x}\rVert_2.

This conjecture says that the logarithmic factor in the general convergence bound is unnecessary for paths. The paper motivates it with numerical experiments, but gives no proof or resolution.

Sources & referencesView supporting material

Primary source

Sam Spiro, “An Averaging Processes on Hypergraphs”, arXiv:2004.13935 (2020).

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.