BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that the 4-state anti-ferromagnetic Potts model with interaction parameter w∈(0,1) on the infinite (d+1)-regular tree has a unique Gibbs measure if w≥1−d+14 for all d≥4. This is tight since it is known that there are multiple Gibbs measures when 0≤w<1−d+14 and d≥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≥1−d+13 when d≥3 and for w∈(0,1) when d=2.
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(m2log(mδ−1)) for graphs G with m edges.
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 ∣λ∣=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 Δ≥3 and edge interaction parameter b∈(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 ∣λ∣=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.
For a graph G=(V,E), k∈N, and a complex number w the partition function of the univariate Potts model is defined as Z(G;k,w):=∑ϕ:V→[k]∏uv∈Eϕ(u)=ϕ(v)w, where [k]:={1,…,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 Δ∈N and any k≥eΔ+1, there exists an open set U in the complex plane that contains the interval [0,1) such that Z(G;k,w)=0 for any w∈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.
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.
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.
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 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≥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.
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.
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.
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.
The number of homomorphisms from a finite graph F to the complete graph Kn 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).
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.
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:=supr∈R∣⟨r,x⟩∣ for x∈H. We show that if W is weakly compact and the orbit space Rk/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.
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.
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)].
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.
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.
We characterize the rank of edge connection matrices of partition functions of real vertex models, as the dimension of the homogeneous components of the algebra of G-invariant tensors. Here G is the sub- group of the real orthogonal group that stabilizes the vertex model. This answers a question of Balázs Szegedy from 2007.
We characterize which graph parameters are partition functions of a vertex model over an algebraically closed field of characteristic 0 (in the sense of de la Harpe and Jones). We moreover characterize when the vertex model can be taken so that its moment matrix has finite rank.
In this paper we prove that the Carathéodory rank of the set of bases of a (poly)matroid is upper bounded by the cardinality of the ground set.
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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.