The Multilevel Splitting algorithm for graph colouring with application to the Potts model. Issue 19 (3rd July 2017)

• Record Type: Journal Article
• Authors: Vaisman, Radislav; Roughan, Matthew; Kroese, Dirk P.
• Is Part Of: Philosophical magazine. Volume 97:Issue 19(2017)
• Page Start: 1646
• Page End: 1673
• Publication Date: 2017-07-03
• Subjects: Partition function -- graph colouring -- Multilevel Splitting -- rare events; Condensed matter -- Periodicals; Physics -- Periodicals; Matière condensée -- Périodiques; Physique -- Périodiques; 530.41
• DOI: 10.1080/14786435.2017.1312023
• Languages: English
• ISSNs: 1478-6435

Abstract

Abstract : Calculating the partition function of the zero-temperature antiferromagnetic model is an important problem in statistical physics. However, an exact calculation is hard since it is strongly connected to a fundamental combinatorial problem of counting proper vertex colourings in undirected graphs, for which an efficient algorithm is not known to exist. Thus, one has to rely on approximation techniques. In this paper, we formulate the problem of the partition function approximation in terms of rare-event probability estimation and investigate the performance of a particle-based algorithm, called Multilevel Splitting, for handling this setting. The proposed method enjoys a provable probabilistic performance guarantee and our numerical study indicates that this algorithm is capable of delivering accurate results using a relatively modest amount of computational resources.