Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Spatial mixing and approximate counting for Potts model on graphs with
  bounded average degree   We propose a notion of contraction function for a family of graphs and
establish its connection to the strong spatial mixing for spin systems. More
specifically, we show that for anti-ferromagnetic Potts model on families of
graphs characterized by a specific contraction function, the model exhibits
strong spatial mixing, and if further the graphs exhibit certain local sparsity
which are very natural and easy to satisfy by typical sparse graphs, then we
also have FPTAS for computing the partition function.
  This new characterization of strong spatial mixing of multi-spin system does
not require maximum degree of the graphs to be bounded, but instead it relates
the decay of correlation of the model to a notion of effective average degree
measured by the contraction of a function on the family of graphs. It also
generalizes other notion of effective average degree which may determine the
strong spatial mixing, such as the connective constant, whose connection to
strong spatial mixing is only known for very simple models and is not
extendable to general spin systems.
  As direct consequences: (1) we obtain FPTAS for the partition function of
$q$-state anti-ferromagnetic Potts model with activity $0\le\beta<1$ on graphs
of maximum degree bounded by $d$ when $q> 3(1-\beta)d+1$, improving the
previous best bound $\beta> 3(1-\beta)d$ and asymptotically approaching the
inapproximability threshold $q=(1-\beta)d$, and (2) we obtain an efficient
sampler (in the same sense of fully polynomial-time almost uniform sampler,
FPAUS) for the Potts model on Erd\H{o}s-R\'enyi random graph
$\mathcal{G}(n,d/n)$ with sufficiently large constant $d$, provided that $q>
3(1-\beta)d+4$. In particular when $\beta=0$, the sampler becomes an FPAUS for
for proper $q$-coloring in $\mathcal{G}(n,d/n)$ with $q> 3d+4$, improving the
current best bound $q> 5.5d$ for FPAUS for $q$-coloring in
$\mathcal{G}(n,d/n)$.

7
The categories of this paper are: hep-th
11
The categories of this paper are: hep-lat
25
The categories of this paper are: patt-sol
10
The categories of this paper are: q-bio
35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
37
The categories of this paper are: supr-con
23
The categories of this paper are: solv-int
31
The categories of this paper are: ao-sci
30
The categories of this paper are: q-alg
8
The categories of this paper are: hep-ex
13
The categories of this paper are: quant-ph
2
The categories of this paper are: math
21
The categories of this paper are: adap-org
19
The categories of this paper are: eess
22
The categories of this paper are: chao-dyn