Davies–Jenssen–Perkins–Roberts minimisation conjecture for the Potts-model program

About 8 years old · traced to

Let GG be a dd-regular graph, let q≥d+1q\ge d+1, let β>0\beta>0, and let UGq(β)U^q_G(\beta) denote the objective associated with the Potts-model linear-programming relaxation. Davies–Jenssen–Perkins–Roberts minimisation conjecture. For d≥3d\ge 3, the minimisation program has optimum given by Kd,dK_{d,d}, and consequently

UKd,dq(β)≤UGq(β)U^q_{K_{d,d}}(\beta)\le U^q_G(\beta)

for every dd-regular graph GG. This is the minimisation part of the conjecture from Davies, Jenssen, Perkins and Roberts. The paper establishes the relevant case d=4d=4 and notes that the statement is open for d≥5d\ge 5.

References

Primary source

Ewan Davies, “Counting proper colourings in 4-regular graphs via the Potts model”, arXiv:1801.07547 (2018).

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.