Star-graph averaging conjecture

Let SnS_n be the star graph on n+1n+1 vertices, and let xx be the weight vector on SnS_n that gives weight 11n+11-\frac{1}{n+1} to the central vertex and weight 1n+1-\frac{1}{n+1} to every other vertex. Define

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

Here x\overline{x} denotes the average-weight vector. Star-graph averaging conjecture. For t=o(nlogn)t=o(n\log n),

E[Δ1(t,x)]xx2.\mathbb{E}[\Delta_1(t,x)]\sim\lVert x-\overline{x}\rVert_2.

The conjecture asserts that the nlognn\log n mixing scale suggested by the general bound is essentially tight for this focused initial condition on a star graph. The paper gives numerical evidence but 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.