2026-07-25T12:50:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23431 2025-10-02T12:54:56Z ddc:004 open_access

Decay of Correlation for Edge Colorings When q > 3Δ Chen, Zejia Wang, Yulin Zhang, Chihao Zhang, Zihan Strong Spatial Mixing Edge Coloring Approximate Counting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zejia Chen and Yulin Wang and Chihao Zhang and Zihan Zhang 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.54 urn:nbn:de:0030-drops-234314 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.54 eng https://creativecommons.org/licenses/by/4.0/legalcode