Counting hypergraph colorings in the local lemma regime

2017/11/09 by Heng Guo, Guo, Heng, Chao Liao +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1711.03396

openalex publication_date 2017/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of q-colorings for k-uniform hypergraphs with maximum degree Δ if k≥ 28 and q >357Δ^(14)/(k-14) . We also obtain a polynomial-time almost uniform sampler if q>931Δ^{(16)/(k-16/3)}. These are the first approximate counting and sampling algorithms in the regime q≪Δ (for large Δ and k) without any additional assumptions. Our method is based on the recent work of Moitra (STOC, 2017). One important contribution of ours is to remove the dependency of k and Δ in Moitra's approach.

Related

• Improved bounds for randomly colouring simple hypergraphs
• Inapproximability of counting hypergraph colourings
• Local Computation Algorithms for Coloring of Uniform Hypergraphs
• Local Computation Algorithms for Hypergraph Coloring -- following Beck's approach (full version)
• Improved bounds for coloring locally sparse hypergraphs