Improved bounds for randomly colouring simple hypergraphs

Weiming Feng; Heng Guo; Jiaheng Wang

doi:10.4230/LIPIcs.APPROX/RANDOM.2022.25

Improved bounds for randomly colouring simple hypergraphs

Weiming Feng, Heng Guo, Jiaheng Wang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ>0, if k≥20(1+δ)δ and q≥100Δ2+δk−4/δ−4, the running time of our algorithm is O~(poly(Δk)⋅n1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Voung, 2021; He, Sun, and Wu, 2021), and does not require Ω(logn) colours unlike the work of Frieze and Anastos (2017).

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Editors	Amit Chakrabarti, Chaitanya Swamy
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-17
Volume	245
ISBN (Electronic)	9783959772495
DOIs	https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.25
Publication status	Published - 15 Sept 2022
Event	RANDOM - Duration: 19 Sept 2022 → 21 Sept 2022 https://randomconference.com/random-2022-home/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
Volume	245
ISSN (Electronic)	1868-8969

Conference

Conference	RANDOM
Period	19/09/22 → 21/09/22
Internet address	https://randomconference.com/random-2022-home/

Keywords / Materials (for Non-textual outputs)

approximate counting
Markov chain
mixing time
hypergraph colouring

Access to Document

10.4230/LIPIcs.APPROX/RANDOM.2022.25Licence: Creative Commons: Attribution (CC-BY)

Improved Bounds_FENG_DOA24062022_VOR_CC-BYFinal published version, 879 KBLicence: Creative Commons: Attribution (CC-BY)

https://drops.dagstuhl.de/opus/volltexte/2022/17147/Licence: Creative Commons: Attribution (CC-BY)

New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

Feng, W., Guo, H., & Wang, J. (2022). Improved bounds for randomly colouring simple hypergraphs. In A. Chakrabarti, & C. Swamy (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) (Vol. 245, pp. 1-17). Article 25 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 245). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.25

Feng, Weiming ; Guo, Heng ; Wang, Jiaheng. / Improved bounds for randomly colouring simple hypergraphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). editor / Amit Chakrabarti ; Chaitanya Swamy. Vol. 245 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 1-17 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{a0f358f88f54431b8b7bdfbc95e11810,

title = "Improved bounds for randomly colouring simple hypergraphs",

abstract = "We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ>0, if k≥20(1+δ)δ and q≥100Δ2+δk−4/δ−4, the running time of our algorithm is O~(poly(Δk)⋅n1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Voung, 2021; He, Sun, and Wu, 2021), and does not require Ω(logn) colours unlike the work of Frieze and Anastos (2017).",

keywords = "approximate counting, Markov chain, mixing time, hypergraph colouring",

author = "Weiming Feng and Heng Guo and Jiaheng Wang",

note = "This project has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No. 947778); RANDOM ; Conference date: 19-09-2022 Through 21-09-2022",

year = "2022",

month = sep,

day = "15",

doi = "10.4230/LIPIcs.APPROX/RANDOM.2022.25",

language = "English",

volume = "245",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--17",

editor = "Amit Chakrabarti and Chaitanya Swamy",

booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)",

url = "https://randomconference.com/random-2022-home/",

}

Feng, W, Guo, H & Wang, J 2022, Improved bounds for randomly colouring simple hypergraphs. in A Chakrabarti & C Swamy (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). vol. 245, 25, Leibniz International Proceedings in Informatics (LIPIcs), vol. 245, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 1-17, RANDOM, 19/09/22. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.25

Improved bounds for randomly colouring simple hypergraphs. / Feng, Weiming; Guo, Heng; Wang, Jiaheng.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). ed. / Amit Chakrabarti; Chaitanya Swamy. Vol. 245 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. p. 1-17 25 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 245).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Improved bounds for randomly colouring simple hypergraphs

AU - Feng, Weiming

AU - Guo, Heng

AU - Wang, Jiaheng

N1 - This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 947778)

PY - 2022/9/15

Y1 - 2022/9/15

N2 - We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ>0, if k≥20(1+δ)δ and q≥100Δ2+δk−4/δ−4, the running time of our algorithm is O~(poly(Δk)⋅n1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Voung, 2021; He, Sun, and Wu, 2021), and does not require Ω(logn) colours unlike the work of Frieze and Anastos (2017).

AB - We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ>0, if k≥20(1+δ)δ and q≥100Δ2+δk−4/δ−4, the running time of our algorithm is O~(poly(Δk)⋅n1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Voung, 2021; He, Sun, and Wu, 2021), and does not require Ω(logn) colours unlike the work of Frieze and Anastos (2017).

KW - approximate counting

KW - Markov chain

KW - mixing time

KW - hypergraph colouring

U2 - 10.4230/LIPIcs.APPROX/RANDOM.2022.25

DO - 10.4230/LIPIcs.APPROX/RANDOM.2022.25

M3 - Conference contribution

VL - 245

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 17

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

A2 - Chakrabarti, Amit

A2 - Swamy, Chaitanya

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

T2 - RANDOM

Y2 - 19 September 2022 through 21 September 2022

ER -

Feng W, Guo H, Wang J. Improved bounds for randomly colouring simple hypergraphs. In Chakrabarti A, Swamy C, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Vol. 245. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2022. p. 1-17. 25. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.APPROX/RANDOM.2022.25

Improved bounds for randomly colouring simple hypergraphs

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this