Counting hypergraph colourings in the local lemma regime

Heng Guo; Chao Liao; Pinyan Lu; Chihao Zhang

doi:10.1137/18M1202955

Counting hypergraph colourings in the local lemma regime

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	1397–1424
Number of pages	25
Journal	SIAM Journal on Computing
Volume	48
Issue number	4
Early online date	1 Aug 2019
DOIs	https://doi.org/10.1137/18M1202955
Publication status	E-pub ahead of print - 1 Aug 2019

Keywords / Materials (for Non-textual outputs)

Lovasz local lemma
approximate counting
sampling
hypergraph coloring

Access to Document

10.1137/18M1202955Licence: All Rights Reserved

hc-sicompAccepted author manuscript, 257 KB

https://epubs.siam.org/doi/pdf/10.1137/18M1202955

1 Conference contribution

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 proceeding › Conference contribution

Open Access
File

Heng Guo
- School of Informatics - Reader in Algorithms and Complexity
- Laboratory for Foundations of Computer Science - Lecturer in Algorithms and Complexity
- Foundations of Computation
Person: Academic: Research Active (Teaching)

Cite this

@article{3ef3636b892b4f32ace77745379e37fc,

title = "Counting hypergraph colourings in the local lemma regime",

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{\textquoteright}s approach.",

keywords = "Lovasz local lemma, approximate counting, sampling, hypergraph coloring",

author = "Heng Guo and Chao Liao and Pinyan Lu and Chihao Zhang",

year = "2019",

month = aug,

day = "1",

doi = "10.1137/18M1202955",

language = "English",

volume = "48",

pages = "1397–1424",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Counting hypergraph colourings in the local lemma regime

AU - Guo, Heng

AU - Liao, Chao

AU - Lu, Pinyan

AU - Zhang, Chihao

PY - 2019/8/1

Y1 - 2019/8/1

N2 - 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.

AB - 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.

KW - Lovasz local lemma

KW - approximate counting

KW - sampling

KW - hypergraph coloring

U2 - 10.1137/18M1202955

DO - 10.1137/18M1202955

M3 - Article

SN - 0097-5397

VL - 48

SP - 1397

EP - 1424

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

Counting hypergraph colourings in the local lemma regime

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Research output

Counting Hypergraph Colourings in the Local Lemma Regime

Profiles

Heng Guo

Cite this