Mark Jerrum
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Mark Jerrum has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Heng Guo
UIUC ETH Zürich UIUC UIUC UIUC UIUC ETH Zürich University of Edinburgh ETH Zürich UIUC
6 shared publications - Martin Dyer
School of Computing University of Leeds Leeds UK
4 shared publications - Haiko Müller
University of Leeds
3 shared publications - Kitty Meeks
School of Mathematical Sciences University of London Queen Mary
2 shared publications - Konrad Anand
School of Mathematical Sciences Queen Mary University of London United Kingdom
2 shared publications - Leslie Ann Goldberg
Department of Computer Science, University of Oxford, Oxford, UK
2 shared publications
Latest Publications
- Open Access
The antiferromagnetic Ising model beyond line graphs
Both the antiferromagnetic Ising model and the hard-core model could be said to be tractable on line graphs of bounded degree. For example, Glauber dynamics is rapidly mixing in both cases. In the case of the hard-core model, we know that tractability extends further, to claw-free graphs and somewhat beyond. In contrast, it is shown here that the corresponding extensions are not possible in the case of the antiferromagnetic Ising model.
Open AccessThe antiferromagnetic Ising model beyond line graphs
Both the antiferromagnetic Ising model and the hard-core model could be said to be tractable on line graphs of bounded degree. For example, Glauber dynamics is rapidly mixing in both cases. In the case of the hard-core model, we know that tractability extends further, to claw-free graphs and somewhat beyond. In contrast, it is shown here that the corresponding extensions are not possible in the case of the antiferromagnetic Ising model.
- Open Access
- 19 September 2025
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 34 (6) , 803-814
Glauber dynamics for the hard-core model on bounded-degree $H$ -free graphsThe hard-core model has as its configurations the independent sets of some graph instance $G$ . The probability distribution on independent sets is controlled by a ‘fugacity’ $\lambda \gt 0$ , with higher $\lambda$ leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph $H$ is excluded as an induced subgraph. If $H$ is a subdivided claw then, for all $\lambda$ , the mixing time is $O(n\log n)$ , where $n$ is the order of $G$ . This extends a result of Chen and Gu for claw-free graphs. When $H$ is a path, the set of possible instances is finite. For all other $H$ , the mixing time is exponential in $n$ for sufficiently large $\lambda$ , depending on $H$ and the maximum degree of $G$ .- 19 September 2025
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 34 (6) , 803-814
Open AccessGlauber dynamics for the hard-core model on bounded-degree $H$ -free graphsThe hard-core model has as its configurations the independent sets of some graph instance $G$ . The probability distribution on independent sets is controlled by a ‘fugacity’ $\lambda \gt 0$ , with higher $\lambda$ leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph $H$ is excluded as an induced subgraph. If $H$ is a subdivided claw then, for all $\lambda$ , the mixing time is $O(n\log n)$ , where $n$ is the order of $G$ . This extends a result of Chen and Gu for claw-free graphs. When $H$ is a path, the set of possible instances is finite. For all other $H$ , the mixing time is exponential in $n$ for sufficiently large $\lambda$ , depending on $H$ and the maximum degree of $G$ . - 2 August 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 13 (1) , 165-189
Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixingWe present a perfect marginal sampler of the unique Gibbs measure of a spin system on \mathbb{Z}^{2} . The algorithm is an adaptation of a previous “lazy depth-first” approach by the authors, but relaxes the requirement of strong spatial mixing to weak. Our result is a step towards methods of efficient sampling using only weak spatial mixing.The work exploits a classical result in statistical physics relating weak spatial mixing on \mathbb{Z}^{2} to strong spatial mixing on squares. When the spin system exhibits weak spatial mixing, the run-time of our sampler is linear in the size of sample. Applications of note are the ferromagnetic Potts model at supercritical temperatures and the ferromagnetic Ising model with consistent non-zero external field at any non-zero temperature.
- 2 August 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 13 (1) , 165-189
Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixingWe present a perfect marginal sampler of the unique Gibbs measure of a spin system on \mathbb{Z}^{2} . The algorithm is an adaptation of a previous “lazy depth-first” approach by the authors, but relaxes the requirement of strong spatial mixing to weak. Our result is a step towards methods of efficient sampling using only weak spatial mixing.The work exploits a classical result in statistical physics relating weak spatial mixing on \mathbb{Z}^{2} to strong spatial mixing on squares. When the spin system exhibits weak spatial mixing, the run-time of our sampler is linear in the size of sample. Applications of note are the ferromagnetic Potts model at supercritical temperatures and the ferromagnetic Ising model with consistent non-zero external field at any non-zero temperature.
- 26 July 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 51 (4) , 1280-1295
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.- 26 July 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 51 (4) , 1280-1295
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.- Open Access
- 5 July 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (3) , 975-990
Counting Vertices of Integral Polytopes Defined by Facets
We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.
- 5 July 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (3) , 975-990
Open AccessCounting Vertices of Integral Polytopes Defined by Facets
We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.
- Open Access
Counting vertices of integral polytopes defined by facets
We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.
Open AccessCounting vertices of integral polytopes defined by facets
We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.
- 12 April 2021
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (6) , 905-921
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the ‘winding’ technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514–527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.
- 12 April 2021
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (6) , 905-921
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the ‘winding’ technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514–527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.
- Open Access
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the "winding" technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514-527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.
Open AccessPolynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the "winding" technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514-527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.
- Open Access
Perfect simulation of the Hard Disks Model by Partial Rejection Sampling
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in $O(\log n)$ rounds, and total time $O(n)$, where $n$ is the expected number of disks. The method extends easily to the hard spheres model in $d>2$ dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.Open AccessPerfect simulation of the Hard Disks Model by Partial Rejection Sampling
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in $O(\log n)$ rounds, and total time $O(n)$, where $n$ is the expected number of disks. The method extends easily to the hard spheres model in $d>2$ dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces. - 3 March 2021
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 8 (2) , 159-177
Perfect simulation of the hard disks model by partial rejection sampling
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O (log n ) rounds, and total time O(n) , where n is the expected number of disks. The method extends easily to the hard spheres model in d > 2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.
- 3 March 2021
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 8 (2) , 159-177
Perfect simulation of the hard disks model by partial rejection sampling
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O (log n ) rounds, and total time O(n) , where n is the expected number of disks. The method extends easily to the hard spheres model in d > 2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.