← All problems

The interchange-process comparison inequality

17 years old · traced to

Let k≥2k\geq 2, let Sk\mathcal S_k be the symmetric group on kk letters, and let g:Sk→Rg:\mathcal S_k\to\mathbb R be any function. For nonnegative numbers γ1,…,γk−1\gamma_1,\ldots,\gamma_{k-1}, with an empty sum interpreted as zero and (ij)∈Sk(ij)\in\mathcal S_k denoting the transposition of ii and jj, the interchange-process comparison conjecture.

∑σ∈Sk∑i=1k−1γi[g(σ)−g((ik)σ)]2≥∑σ∈Sk∑1≤i<j≤k−1γiγjγ1+⋯+γk−1[g(σ)−g((ij)σ)]2.\sum_{\sigma\in\mathcal S_k}\sum_{i=1}^{k-1}\gamma_i\bigl[g(\sigma)-g((ik)\sigma)\bigr]^2\geq\sum_{\sigma\in\mathcal S_k}\sum_{1\leq i<j\leq k-1}\frac{\gamma_i\gamma_j}{\gamma_1+\cdots+\gamma_{k-1}}\bigl[g(\sigma)-g((ij)\sigma)\bigr]^2.

This inequality was proposed as a tool for controlling spectral changes in an induction argument for Aldous' conjecture, when a new vertex has degree k−1k-1. The supplied context describes it as a conjecture and says that the broader Aldous conjecture had been resolved, but gives no resolution status for this inequality itself.

References

Status

  • Solved: Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer. Proof of Aldous' spectral gap conjecture (Journal of the American Mathematical Society 23 (2010), no. 3, 831–851, 2010) https://arxiv.org/abs/0906.1238

Source: A. B. Dieker, “Interlacings for random walks on weighted graphs and the interchange process”, arXiv:0906.1716 (2009).

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.