Counting hypergraph colourings in the local lemma regime

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of q-colourings 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.
Original languageEnglish
Pages (from-to)1397–1424
Number of pages25
JournalSIAM Journal on Computing
Volume48
Issue number4
Early online date1 Aug 2019
DOIs
Publication statusE-pub ahead of print - 1 Aug 2019

Keywords

  • Lovasz local lemma
  • approximate counting
  • sampling
  • hypergraph coloring

Fingerprint Dive into the research topics of 'Counting hypergraph colourings in the local lemma regime'. Together they form a unique fingerprint.

  • Counting Hypergraph Colourings in the Local Lemma Regime

    Guo, H., Liao, C., Lu, P. & Zhang, C., 29 Jun 2018, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM, p. 926-939 14 p. (STOC 2018).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    File

Cite this