2025/08/05 by Jun-Ting Hsieh, Hsieh, Jun-Ting
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2508.03093
We present a new algorithm for finding large independent sets in 3-colorable graphs with small 1-sided threshold rank. Specifically, given an n-vertex 3-colorable graph whose uniform random walk matrix has at most r eigenvalues larger than ε, our algorithm finds a proper 3-coloring on at least ((1)/(2)-O(ε))n vertices in time nO(r/ε2). This extends and improves upon the result of Bafna, Hsieh, and Kothari on 1-sided expanders. Furthermore, an independent work by Buhai, Hua, Steurer, and Vári-Kakas shows that it is UG-hard to properly 3-color more than ((1)/(2)+ε)n vertices, thus establishing the tightness of our result. Our proof is short and simple, relying on the observation that for any distribution over proper 3-colorings, the correlation across an edge must be large if the marginals of the endpoints are not concentrated on any single color. Notably, this property fails for 4-colorings, which is consistent with the hardness result of [BHK25] for 4-colorable 1-sided expanders.