Guus Regts
YOU?
Author Swipe
View article: On zeros and algorithms for disordered systems: mean-field spin glasses
On zeros and algorithms for disordered systems: mean-field spin glasses Open
Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statistical inference. In the mean-field setting, we design determi…
View article: Barvinok's interpolation method meets Weitz's correlation decay approach
Barvinok's interpolation method meets Weitz's correlation decay approach Open
In this paper we take inspiration from Weit'z algorithm for approximating the independence polynomial to provide a new algorithm for computing the coefficients of the Taylor series of the logarithm of the independence polynomial. Hereby we…
View article: Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs Open
We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $χ_G(x)$, lie inside the disk centered at $0$ of radius $4.25 Δ(G)$, where $Δ(G)$ denote the maximum degree of $G$. This improves on a recent result of Jensse…
View article: A near-optimal zero-free disk for the Ising model
A near-optimal zero-free disk for the Ising model Open
The partition function of the Ising model of a graph \\(G=(V,E)\\) is defined as \\(Z_{\\operatorname{Ising}}(G;b)=\\sum_{\\sigma:V\\to \\{0,1\\}} b^{m(\\sigma)}\\), where \\(m(\\sigma)\\) denotes the number of edges \\(e=\\{u,v\\}\\) such…
View article: Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros Open
Let $Δ,q\geq 3$ be integers. We prove that there exists $η\geq 0.002$ such that if $q\geq (2-η)Δ$, then there exists an open set $\mathcal{U}\subset \mathbb{C}$ that contains the interval $[0,1]$ such that for each $w\in \mathcal{U}$ and a…
View article: Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem Open
We prove that for any graph G of maximum degree at most Δ, the zeros of its chromatic polynomial χG(x) (in C) lie inside the disc of radius 5.94Δ centered at 0. This improves on the previously best known bound of approximately 6.91Δ. We al…
View article: Approximating the volume of a truncated relaxation of the independence polytope
Approximating the volume of a truncated relaxation of the independence polytope Open
Answering a question of Gamarnik and Smedira, we give a polynomial time algorithm that approximately computes the volume of a truncation of a relaxation of the independent set polytope, improving on their quasi-polynomial time algorithm. O…
View article: A near-optimal zero-free disk for the Ising model
A near-optimal zero-free disk for the Ising model Open
The partition function of the Ising model of a graph $G=(V,E)$ is defined as $Z_{\text{Ising}}(G;b)=\sum_{σ:V\to \{0,1\}} b^{m(σ)}$, where $m(σ)$ denotes the number of edges $e=\{u,v\}$ such that $σ(u)=σ(v)$. We show that for any positive …
View article: Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees Open
We show that the anti-ferromagnetic Potts model on trees exhibits strong spatial mixing for a near-optimal range of parameters. Our work complements recent results of Chen, Liu, Mani, and Moitra [arXiv.2304.01954] who showed this to be tru…
View article: Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem Open
We prove that for any graph $G$ of maximum degree at most $Δ$, the zeros of its chromatic polynomial $χ_G(x)$ (in $\mathbb{C}$) lie inside the disc of radius $5.94 Δ$ centered at $0$. This improves on the previously best known bound of app…
View article: Uniqueness of the Gibbs Measure for the Anti-ferromagnetic Potts Model on the Infinite $$\Delta $$-Regular Tree for Large $$\Delta $$
Uniqueness of the Gibbs Measure for the Anti-ferromagnetic Potts Model on the Infinite $$\Delta $$-Regular Tree for Large $$\Delta $$ Open
In this paper we prove that for any integer $$q\ge 5$$ , the anti-ferromagnetic q -state Potts model on the infinite $$\Delta $$ -regular tree has a unique Gibbs measure for all edge interaction parameters $$w\in [1-q/\Delta ,1)$$ , pro…
View article: On the Location of Chromatic Zeros of Series-Parallel Graphs
On the Location of Chromatic Zeros of Series-Parallel Graphs Open
In this paper we consider the zeros of the chromatic polynomial of series-parallel graphs. Complementing a result of Sokal, giving density outside the disk $|q-1|\leq1$, we show density of these zeros in the half plane $\Re(q)>3/2$ and we …
View article: On boundedness of zeros of the independence polynomial of tori
On boundedness of zeros of the independence polynomial of tori Open
We study boundedness of zeros of the independence polynomial of tori for sequences of tori converging to the integer lattice. We prove that zeros are bounded for sequences of balanced tori, but unbounded for sequences of highly unbalanced …
View article: Absence of zeros implies strong spatial mixing
Absence of zeros implies strong spatial mixing Open
In this paper we show that absence of complex zeros of the partition function of the hard-core model on any family of bounded degree graphs that is closed under taking induced subgraphs implies that the associated probability measure, the …
View article: Approximate counting using Taylor's theorem: a survey
Approximate counting using Taylor's theorem: a survey Open
In this article we consider certain well-known polynomials associated with graphs including the independence polynomial and the chromatic polynomial. These polynomials count certain objects in graphs: independent sets in the case of the in…
View article: Approximating the chromatic polynomial is as hard as computing it exactly
Approximating the chromatic polynomial is as hard as computing it exactly Open
We show that for any non-real algebraic number $q$ such that $|q-1|>1$ or $\Re(q)>\frac{3}{2}$ it is \textsc{\#P}-hard to compute a multiplicative (resp. additive) approximation to the absolute value (resp. argument) of the chromatic polyn…
View article: Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree
Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree Open
We show that the $4$ -state anti-ferromagnetic Potts model with interaction parameter $w\in (0,1)$ on the infinite $(d+1)$ -regular tree has a unique Gibbs measure if $w\geq 1-\dfrac{4}{d+1_{_{\;}}}$ for all $d\geq 4$ . This is tight since…
View article: Polynomials and graph homomorphisms
Polynomials and graph homomorphisms Open
We develop in the language of graph homomorphisms the connection between the Tutte polynomial and the state models of statistical physics.
\n• The Tutte polynomial and homomorphism numbers.
\n• Spin models and edge coloring models.
\n• Con…
View article: On the location of chromatic zeros of series-parallel graphs
On the location of chromatic zeros of series-parallel graphs Open
In this paper we consider the zeros of the chromatic polynomial of series-parallel graphs. Complementing a result of Sokal, showing density outside the disk $|q-1|\leq1$, we show density of these zeros in the half plane $\Re(q)>3/2$ and we…
View article: Sampling from the low temperature Potts model through a Markov chain on flows
Sampling from the low temperature Potts model through a Markov chain on flows Open
In this article, we consider the algorithmic problem of sampling from the Potts model and computing its partition function at low temperatures. Instead of directly working with spin configurations, we consider the equivalent problem of sam…
View article: Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $Δ$-regular tree for large $Δ$
Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $Δ$-regular tree for large $Δ$ Open
In this paper we prove that for any integer $q\geq 5$, the anti-ferromagnetic $q$-state Potts model on the infinite $Δ$-regular tree has a unique Gibbs measure for all edge interaction parameters $w\in [1-q/Δ,1)$, provided $Δ$ is large eno…
View article: Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs Open
We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter $\lambda $ on the unit circle in the complex plane. Complex-valued parameters for the Ising mo…
View article: Absence of zeros implies strong spatial mixing
Absence of zeros implies strong spatial mixing Open
In this paper we show that absence of complex zeros of the partition function of the hard-core model on any family of bounded degree graphs implies that the associated probability measure, the \emph{hard-core measure}, satisfies strong spa…
View article: Some Applications of Wagner's Weighted Subgraph Counting Polynomial
Some Applications of Wagner's Weighted Subgraph Counting Polynomial Open
We use Wagner's weighted subgraph counting polynomial to prove that the partition function of the anti-ferromagnetic Ising model on line graphs is real rooted and to prove that roots of the edge cover polynomial have absolute value at most…
View article: On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs Open
For a graph G=(V,E) , k\in \mathbb{N} , and complex numbers w=(w_e)_{e\in E} the partition function of the multivariate Potts model is defined as \mathbf{Z}(G;k,w):=\sum_{\phi\colon V\to [k]} \prod_{\substack{e=uv\in E \\ \phi(u)=\phi(v)}}…
View article: Improved bounds for zeros of the chromatic polynomial on bounded degree graphs
Improved bounds for zeros of the chromatic polynomial on bounded degree graphs Open
We prove that for any graph $G$ of maximum degree at most $Δ$, the zeros of its chromatic polynomial $χ_G(z)$ (in $\mathbb{C}$) lie outside the disk of radius $5.02 Δ$ centered at $0$. This improves on the previously best known bound of ap…
View article: Improved bounds for zeros of the chromatic polynomial on bounded degree\n graphs
Improved bounds for zeros of the chromatic polynomial on bounded degree\n graphs Open
We prove that for any graph $G$ of maximum degree at most $\\Delta$, the zeros\nof its chromatic polynomial $\\chi_G(z)$ (in $\\mathbb{C}$) lie outside the disk\nof radius $5.02 \\Delta$ centered at $0$. This improves on the previously bes…
View article: Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial Open
The independence polynomial originates in statistical physics as the partition function of the hard-core model. The location of the complex zeros of the polynomial is related to phase transitions, and plays an important role in the design …
View article: Mixed partition functions and exponentially bounded edge-connection rank
Mixed partition functions and exponentially bounded edge-connection rank Open
We study graph parameters whose associated edge-connection matrices have exponentially bounded rank growth. Our main result is an explicit construction of a large class of graph parameters with this property that we call mixed partition fu…