색채 샘플링을 위한 플립 동역학: 단순한 메트릭을 사용하여 (11/6-) 개선하기

우리는 최대 차수를 가진 그래프의 k-색채를 무작위로 샘플링하기 위한 개선된 경계를 제시합니다. 우리의 결과는 그래프에 대한 추가 가정 없이 유효합니다. Glauber 동역학은 단순한 단일 사이트 업데이트 마르코프 체인입니다. Jerrum(1995)은 k>2일 때 입력 그래프의 최대 차수가 있을 때 Glauber 동역학의 최적 O(nn) 혼합 시간 경계를 증명했습니다. 이 경계는 Vigoda(1999)에 의해 작은 최대 2-색상 요소를 매 단계 재색칠하는 "플립" 동역학을 사용하여 k > (11/6)로 개선되었습니다. Vigoda의 결과는 Chen et al.(2019)가 k > (11/6 -)에 대해 플립 동역학의 최적 혼합을 확립할 때까지 20년 동안 일반 그래프에 대해 알려진 최선이었습니다. 우리는 이러한 결과에 대한 첫 번째 실질적인 개선을 제시합니다. 우리는 k가 1.809일 때 플립 동역학에 대한 최적 혼합 시간 경계 O(nn)을 증명합니다. 이는 최근 스펙트럼 독립성 결과를 통해 같은 범위의 k에 대해 Glauber 동역학에 대한 최적 O(nn) 혼합 시간을 제공합니다/일 때 =O(1). 우리의 증명은 "차단되지 않은" 이웃에 대한 단순 가중 해밍 거리와 함께 경로 결합을 활용합니다.