65
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Deterministic counting of graph colourings using sequences of subgraphs

      Preprint

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          In this paper we propose a deterministic algorithm for approximately counting the \(k\)-colourings of sparse random graphs \(G(n,d/n)\). In particular, our algorithm computes in polynomial time a \((1\pm n^{-\Omega(1)})\)approximation of the logarithm of the number of \(k\)-colourings of \(G(n,d/n)\) for \(k\geq (2+\epsilon) d\) with high probability over the graph instances. Our algorithm is related to the algorithms of A. Bandyopadhyay et al. in SODA '06, and A. Montanari et al. in SODA '06, i.e. it uses {\em spatial correlation decay} to compute {\em deterministically} marginals of {\em Gibbs distribution}. We develop a scheme whose accuracy depends on {\em non-reconstruction} of the colourings of \(G(n,d/n)\), rather than {\em uniqueness} that are required in previous works. This leaves open the possibility for our schema to be sufficiently accurate even for \(k

          Related collections

          Author and article information

          Journal
          0909.5224
          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Discrete mathematics & Graph theory
          Discrete mathematics & Graph theory

          Comments

          Comment on this article