Counting hypergraph colourings in the local lemma regime

DOI10.1145/3188745.3188934zbMath1428.05294OpenAlexW2962990085MaRDI QIDQ5230351

Pinyan Lu, Chao Liao, Heng Guo, Chihao Zhang

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/76046048/Counting_Hypergraph_Colourings_in_the_Local_Lemma_Regime.pdf

zbMATH Keywords

approximate countingLovász local lemma

Mathematics Subject Classification ID

Hypergraphs (05C65) Enumeration in graph theory (05C30) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs

This page was built for publication: Counting hypergraph colourings in the local lemma regime