The Ising Antiferromagnet and Max Cut on Random Regular Graphs.

Amin Coja-Oghlan Philipp Loick Balázs F. Mezei Gregory B. Sorkin

Published in: SIAM J. Discret. Math. (2022)

Keyphrases

max cut
graph model
np complete problems
planar graphs
spectral graph
graph partitioning
phase transition
np hard
markov random field
partition function
clustering algorithm
upper bound
np complete
constraint satisfaction
min max
theoretic framework