File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.4230/LIPIcs.APPROX/RANDOM.2022.25
- Scopus: eid_2-s2.0-85139106764
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Improved Bounds for Randomly Colouring Simple Hypergraphs
| Title | Improved Bounds for Randomly Colouring Simple Hypergraphs |
|---|---|
| Authors | |
| Keywords | Approximate counting Hypergraph colouring Markov chain Mixing time |
| Issue Date | 2022 |
| Citation | Leibniz International Proceedings in Informatics, LIPIcs, 2022, v. 245, article no. 25 How to Cite? |
| 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 Õ(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 Vuong, 2021; He, Sun, and Wu, 2021), and does not require Ω(log n) colours unlike the work of Frieze and Anastos (2017). |
| Persistent Identifier | http://hdl.handle.net/10722/354984 |
| ISSN | 2023 SCImago Journal Rankings: 0.796 |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Feng, Weiming | - |
| dc.contributor.author | Guo, Heng | - |
| dc.contributor.author | Wang, Jiaheng | - |
| dc.date.accessioned | 2025-03-21T09:10:27Z | - |
| dc.date.available | 2025-03-21T09:10:27Z | - |
| dc.date.issued | 2022 | - |
| dc.identifier.citation | Leibniz International Proceedings in Informatics, LIPIcs, 2022, v. 245, article no. 25 | - |
| dc.identifier.issn | 1868-8969 | - |
| dc.identifier.uri | http://hdl.handle.net/10722/354984 | - |
| dc.description.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 Õ(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 Vuong, 2021; He, Sun, and Wu, 2021), and does not require Ω(log n) colours unlike the work of Frieze and Anastos (2017). | - |
| dc.language | eng | - |
| dc.relation.ispartof | Leibniz International Proceedings in Informatics, LIPIcs | - |
| dc.subject | Approximate counting | - |
| dc.subject | Hypergraph colouring | - |
| dc.subject | Markov chain | - |
| dc.subject | Mixing time | - |
| dc.title | Improved Bounds for Randomly Colouring Simple Hypergraphs | - |
| dc.type | Conference_Paper | - |
| dc.description.nature | link_to_subscribed_fulltext | - |
| dc.identifier.doi | 10.4230/LIPIcs.APPROX/RANDOM.2022.25 | - |
| dc.identifier.scopus | eid_2-s2.0-85139106764 | - |
| dc.identifier.volume | 245 | - |
| dc.identifier.spage | article no. 25 | - |
| dc.identifier.epage | article no. 25 | - |