BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Guus Regts

Guus Regts appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COData Structures and Algorithmsmath-phmath.MPDiscrete MathematicsComputational Complexitymath.FAmath.PRmath.QAmath.RAmath.RTmath.AGmath.CVmath.DSmath.OC

Catalog footprint

What is connected

21works
15topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2023arXiv

Uniqueness of the Gibbs measure for the $4$-state anti-ferromagnetic Potts model on the regular tree

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-\frac{4}{d+1}$ for all $d\geq 4$. This is tight since it is known that there are multiple Gibbs measures when $0\leq w<1-\frac{4}{d+1}$ and $d\geq 4$. We moreover give a new proof of the uniqueness of the Gibbs measure for the $3$-state Potts model on the $(d+1)$-regular tree for $w\geq 1-\frac{3}{d+1}$ when $d\geq 3$ and for $w\in (0,1)$ when $d=2$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sampling from the low temperature Potts model through a Markov chain on flows

In this paper 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 sampling flows. We show, using path coupling, that a simple and natural Markov chain on the set of flows is rapidly mixing. As a result we find a $δ$-approximate sampling algorithm for the Potts model at low enough temperatures, whose running time is bounded by $O(m^2\log(mδ^{-1}))$ for graphs $G$ with $m$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter $λ$ on the unit circle in the complex plane. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all $|λ|\neq 1$ by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens around $λ=1$, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point $λ=1$, and more generally on the entire unit circle. For an integer $Δ\geq 3$ and edge interaction parameter $b\in (0,1)$ we show #P-hardness for approximating the partition function on graphs of maximum degree $Δ$ on the arc of the unit circle where the Lee-Yang zeros are dense. This result contrasts with known approximation algorithms when $|λ|\neq 1$ or when $λ$ is in the complementary arc around $1$ of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee-Yang zeros and the tractability of efficiently approximating the partition function on bounded-degree graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs

For a graph $G=(V,E)$, $k\in \mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as \[ {\bf Z}(G;k,w):=\sum_{ϕ:V\to [k]}\prod_{\substack{uv\in E \\ ϕ(u)=ϕ(v)}}w, \] where $[k]:=\{1,\ldots,k\}$. In this paper we give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any $Δ\in \mathbb{N}$ and any $k\geq eΔ+1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${\bf Z}(G;k,w)\neq 0$ for any $w\in U$ and any graph $G$ of maximum degree at most $Δ$. (Here $e$ denotes the base of the natural logarithm.) For small values of $Δ$ we are able to give better results. As an application of our results we obtain improved bounds on $k$ for the existence of deterministic approximation algorithms for counting the number of proper $k$-colourings of graphs of small maximum degree.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Mixed partition functions and exponentially bounded edge-connection rank

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 functions. Mixed partition functions can be seen as a generalization of partition functions of vertex models, as introduced by de la Harpe and Jones, [P. de la Harpe, V.F.R. Jones, Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory, Series B 57 (1993) 207--227] and they are related to invariant theory of orthosymplectic supergroup. We moreover show that evaluations of the characteristic polynomial of a simple graph are examples of mixed partition functions, answering a question of de la Harpe and Jones.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tutte's dichromate for signed graphs

We introduce the ``trivariate Tutte polynomial" of a signed graph as an invariant of signed graphs up to vertex switching that contains among its evaluations the number of proper colorings and the number of nowhere-zero flows. In this, it parallels the Tutte polynomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations. The number of nowhere-zero tensions (for signed graphs they are not simply related to proper colorings as they are for graphs) is given in terms of evaluations of the trivariate Tutte polynomial at two distinct points. Interestingly, the bivariate dichromatic polynomial of a biased graph, shown by Zaslavsky to share many similar properties with the Tutte polynomial of a graph, does not in general yield the number of nowhere-zero flows of a signed graph. Therefore the ``dichromate" for signed graphs (our trivariate Tutte polynomial) differs from the dichromatic polynomial (the rank-size generating function). The trivariate Tutte polynomial of a signed graph can be extended to an invariant of ordered pairs of matroids on a common ground set -- for a signed graph, the cycle matroid of its underlying graph and its frame matroid form the relevant pair of matroids. This invariant is the canonically defined Tutte polynomial of matroid pairs on a common ground set in the sense of a recent paper of Krajewski, Moffatt and Tanasa, and was first studied by Welsh and Kayibi as a four-variable linking polynomial of a matroid pair on a common ground set.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Location of zeros for the partition function of the Ising model on bounded degree graphs

The seminal Lee-Yang theorem states that for any graph the zeros of the partition function of the ferromagnetic Ising model lie on the unit circle in $\mathbb C$. In fact the union of the zeros of all graphs is dense on the unit circle. In this paper we study the location of the zeros for the class of graphs of bounded maximum degree $d\geq 3$, both in the ferromagnetic and the anti-ferromagnetic case. We determine the location exactly as a function of the inverse temperature and the degree $d$. An important step in our approach is to translate to the setting of complex dynamics and analyze a dynamical system that is naturally associated to the partition function.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Statistical physics approaches to Unique Games

We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

A Tutte polynomial for maps

We follow the example of Tutte in his construction of the dichromate of a graph (that is, the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial in order to construct a new polynomial invariant of maps (graphs embedded in orientable surfaces). We call this the surface Tutte polynomial. The surface Tutte polynomial of a map contains the Las Vergnas polynomial, Bollobás-Riordan polynomial and Kruskhal polynomial as specializations. By construction, the surface Tutte polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Graph parameters from symplectic group invariants

In this paper we introduce, and characterize, a class of graph parameters obtained from tensor invariants of the symplectic group. These parameters are similar to partition functions of vertex models, as introduced by de la Harpe and Jones, [P. de la Harpe, V.F.R. Jones, Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory, Series B 57 (1993) 207-227]. Yet they give a completely different class of graph invariants. We moreover show that certain evaluations of the cycle partition polynomial, as defined by Martin [P. Martin, Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck, Diss. Institut National Polytechnique de Grenoble-INPG; Université Joseph-Fourier-Grenoble I, 1977], give examples of graph parameters that can be obtained this way.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Matroid invariants and counting graph homomorphisms

The number of homomorphisms from a finite graph $F$ to the complete graph $K_n$ is the evaluation of the chromatic polynomial of $F$ at $n$. Suitably scaled, this is the Tutte polynomial evaluation $T(F;1-n,0)$ and an invariant of the cycle matroid of $F$. De la Harpe and Jaeger \cite{dlHJ95} asked more generally when is it the case that a graph parameter obtained from counting homomorphisms from $F$ to a fixed graph $G$ depends only on the cycle matroid of $F$. They showed that this is true when $G$ has a generously transitive automorphism group (examples include Cayley graphs on an abelian group, and Kneser graphs). Using tools from multilinear algebra, we prove the converse statement, thus characterizing finite graphs $G$ for which counting homomorphisms to $G$ yields a matroid invariant. We also extend this result to finite weighted graphs $G$ (where to count homomorphisms from $F$ to $G$ includes such problems as counting nowhere-zero flows of $F$ and evaluating the partition function of an interaction model on $F$).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On partition functions for 3-graphs

A {\em cyclic graph} is a graph with at each vertex a cyclic order of the edges incident with it specified. We characterize which real-valued functions on the collection of cubic cyclic graphs are partition functions of a real vertex model (P. de la Harpe, V.F.R. Jones, Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory, Series B 57 (1993) 207--227). They are characterized by `weak reflection positivity', which amounts to the positive semidefiniteness of matrices based on the `$k$-join' of cubic cyclic graphs (for all $k\in\oZ_+$). Basic tools are the representation theory of the symmetric group and geometric invariant theory, in particular the Hanlon-Wales theorem on the decomposition of Brauer algebras and the Procesi-Schwarz theorem on inequalities defining orbit spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Compact orbit spaces in Hilbert spaces and limits of edge-colouring models

Let $G$ be a group of orthogonal transformations of a real Hilbert space $H$. Let $R$ and $W$ be bounded $G$-stable subsets of $H$. Let $\|.\|_R$ be the seminorm on $H$ defined by $\|x\|_R:=\sup_{r\in R}|\langle r,x\rangle|$ for $x\in H$. We show that if $W$ is weakly compact and the orbit space $R^k/G$ is compact for each $k\in\oN$, then the orbit space $W/G$ is compact when $W$ is equiped with the norm topology induced by $\|.\|_R$. As a consequence we derive the existence of limits of edge-colouring models which answers a question posed by Lovász. It forms the edge-colouring counterpart of the graph limits of Lovász and Szegedy, which can be seen as limits of vertex-colouring models. In the terminology of de la Harpe and Jones, vertex- and edge-colouring models are called `spin models' and `vertex models' respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the existence of real R-matrices for virtual link invariants

We characterize the virtual link invariants that can be described as partition function of a real-valued R-matrix, by being weakly reflection positive. Weak reflection positivity is defined in terms of joining virtual link diagrams, which is a specialization of joining virtual link diagram tangles. Basic techniques are the first fundamental theorem of invariant theory, the Hanlon-Wales theorem on the decomposition of Brauer algebras, and the Procesi-Schwarz theorem on inequalities for closed orbits.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Regularity lemmas in a Banach space setting

Szemerédi's regularity lemma is a fundamental tool in extremal graph theory, theoretical computer science and combinatorial number theory. Lovász and Szegedy [L. Lovász and B. Szegedy: Szemerédi's Lemma for the analyst, Geometric and Functional Analysis 17 (2007), 252-270] gave a Hilbert space interpretation of the lemma and an interpretation in terms of compact- ness of the space of graph limits. In this paper we prove several compactness results in a Banach space setting, generalising results of Lovász and Szegedy as well as a result of Borgs, Chayes, Cohn and Zhao [C. Borgs, J.T. Chayes, H. Cohn and Y. Zhao: An Lp theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions, arXiv preprint arXiv:1401.2906 (2014)].

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Edge-reflection positivity and weighted graph homomorphisms

B. Szegedy [Edge coloring models and reflection positivity, {\sl Journal of the American Mathematical Society} {\bf 20} (2007) 969--988] showed that the number of homomorphisms into a weighted graph is equal to the partition function of a complex edge-coloring model. Using some results in geometric invariant theory, we characterize for which weighted graphs the edge-coloring model can be taken to be real valued that is, we characterize for which weighted graphs the number of homomorphisms into them are edge-reflection positive. In particular, we determine explicitly for which simple graphs the number of homomorphisms into them is equal to the partition function of a real edge-coloring model. This answers a question posed by Szegedy.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tensor invariants for certain subgroups of the orthogonal group

Let V be an n-dimensional vector space and let On be the orthogonal group. Motivated by a question of B. Szegedy (B. Szegedy, Edge coloring models and reflection positivity, Journal of the American Mathematical Society Volume 20, Number 4, 2007), about the rank of edge connection matrices of partition functions of vertex models, we give a combinatorial parameterization of tensors in V \otimes k invariant under certain subgroups of the orthogonal group. This allows us to give an answer to this question for vertex models with values in an algebraically closed field of characteristic zero.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Polyhedra with the Integer Caratheodory Property

A polyhedron P has the Integer Caratheodory Property if the following holds. For any positive integer k and any integer vector w in kP, there exist affinely independent integer vectors x_1,...,x_t in P and positive integers n_1,...,n_t such that n_1+...+n_t=k and w=n_1x_1+...+n_tx_t. In this paper we prove that if P is a (poly)matroid base polytope or if P is defined by a TU matrix, then P and projections of P satisfy the integer Caratheodory property.

0 citations0 reviewsNo code linkedOpen access