4
[2307.08080] Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
source link: https://arxiv.org/abs/2307.08080
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 16 Jul 2023 (v1), last revised 22 Mar 2024 (this version, v2)]
Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors
We prove that the single-site Glauber dynamics for sampling proper q-colorings mixes in OΔ(nlogn) time on line graphs with n vertices and maximum degree Δ when q>(1+o(1))Δ. The main tool in our proof is the matrix trickle-down theorem developed by Abdolazimi, Liu and Oveis Gharan (FOCS, 2021).
| Comments: | 28 pages |
| Subjects: | Data Structures and Algorithms (cs.DS); Probability (math.PR) |
| Cite as: | arXiv:2307.08080 [cs.DS] |
| (or arXiv:2307.08080v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2307.08080 |
Submission history
From: Yulin Wang [view email][v1] Sun, 16 Jul 2023 15:34:04 UTC (32 KB)
[v2] Fri, 22 Mar 2024 14:03:18 UTC (34 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK