2026-07-20T11:02:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21040 2024-09-16T06:02:39Z ddc:004 open_access

Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3 Chang, Evan Kolhe, Neel Sohn, Youngtak Random constraint satisfaction problem replica symmetry breaking interpolation bound For a large class of random constraint satisfaction problems (csp), deep but non-rigorous theory from statistical physics predict the location of the sharp satisfiability transition. The works of Ding, Sly, Sun (2014, 2016) and Coja-Oghlan, Panagiotou (2014) established the satisfiability threshold for random regular k-nae-sat, random k-sat, and random regular k-sat for large enough k ≥ k₀ where k₀ is a large non-explicit constant. Establishing the same for small values of k ≥ 3 remains an important open problem in the study of random csps. In this work, we study two closely related models of random csps, namely the 2-coloring on random d-regular k-uniform hypergraphs and the random d-regular k-nae-sat model. For every k ≥ 3, we prove that there is an explicit d_⋆(k) which gives a satisfiability upper bound for both of the models. Our upper bound d_⋆(k) for k ≥ 3 matches the prediction from statistical physics for the hypergraph 2-coloring by Dall’Asta, Ramezanpour, Zecchina (2008), thus conjectured to be sharp. Moreover, d_⋆(k) coincides with the satisfiability threshold of random regular k-nae-sat for large enough k ≥ k₀ by Ding, Sly, Sun (2014). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Evan Chang and Neel Kolhe and Youngtak Sohn 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.47 urn:nbn:de:0030-drops-210402 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.47 eng https://creativecommons.org/licenses/by/4.0/legalcode