Path-graph averaging conjecture without a logarithmic factor

About 6 years old · traced to

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

Δ1(t,x)=∥RPnt(x)−x‾∥1,\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)]≤e−c∥x−x‾∥2.\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.

References

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.