DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.54

Decay of Correlation for Edge Colorings When q > 3Δ

Authors: Zejia Chen, Yulin Wang, Chihao Zhang, and Zihan Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We examine various perspectives on the decay of correlation for the uniform distribution over proper q-edge colorings of graphs with maximum degree Δ. First, we establish the coupling independence property when q ≥ 3Δ for general graphs. Together with the recent work of Chen, Feng, Guo, Zhang and Zou (2024), this result implies a fully polynomial-time approximation scheme (FPTAS) for counting the number of proper q-edge colorings. Next, we prove the strong spatial mixing property on trees, provided that q > (3+o(1))Δ. The strong spatial mixing property is derived from the spectral independence property of a version of the weighted edge coloring distribution, which is established using the matrix trickle-down method developed in Abdolazimi, Liu and Oveis Gharan (FOCS, 2021) and Wang, Zhang and Zhang (STOC, 2024). Finally, we show that the weak spatial mixing property holds on trees with maximum degree Δ if and only if q ≥ 2Δ-1.

Cite as

Zejia Chen, Yulin Wang, Chihao Zhang, and Zihan Zhang. Decay of Correlation for Edge Colorings When q > 3Δ. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.54,
  author =	{Chen, Zejia and Wang, Yulin and Zhang, Chihao and Zhang, Zihan},
  title =	{{Decay of Correlation for Edge Colorings When q \rangle 3\Delta}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.54},
  URN =		{urn:nbn:de:0030-drops-234314},
  doi =		{10.4230/LIPIcs.ICALP.2025.54},
  annote =	{Keywords: Strong Spatial Mixing, Edge Coloring, Approximate Counting}
}

Search Results

Documents authored by Wang, Yulin

Decay of Correlation for Edge Colorings When q > 3Δ

Abstract

Cite as

Thanks for your feedback!

Could not send message