Replica-symmetry MP-structure conjecture for the independent set problem

Let (β,h,γ)(\beta,h,\gamma) be parameters of the independent set problem, and let an MP-structure consist of a hierarchy (ζ,Vm)(\zeta,\mathcal V_{\boldsymbol m}) with KK levels. For such a structure, write RN,β,h,γ(S)R_{N,\beta,h,\gamma}(\mathcal S) for the rest-term in the interpolation formula, where S=(ζ,Vm)\mathcal S=(\zeta,\mathcal V_{\boldsymbol m}). Replica-symmetry MP-structure conjecture. For every (β,h,γ)(\beta,h,\gamma) there exists a unique KK^\star-level MP-structure S=S(β,h,γ)=(ζ,Vm)\mathcal S^\star=\mathcal S^\star(\beta,h,\gamma)=(\zeta^\star,\mathcal V^\star_{\boldsymbol m}) such that

limNRN,β,h,γ(S)=0.\lim_{N\to\infty}R_{N,\beta,h,\gamma}(\mathcal S^\star)=0.

The case K=K^\star=\infty is also possible. This conjecture asserts that the limiting free energy is captured by a unique hierarchical MP-structure through the vanishing of the interpolation remainder, which is the key step in describing the replica-symmetry phase of the independent set problem.

Sources & referencesView supporting material

Primary source

Nicola Kistler and Marius A. Schmidt, “On the replica symmetry phase of the independent set problem”, arXiv:1512.04462 (2015).

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.