DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.47

Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3

Authors: Evan Chang, Neel Kolhe, and Youngtak Sohn

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

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).

Cite as

Evan Chang, Neel Kolhe, and Youngtak Sohn. Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.APPROX/RANDOM.2024.47,
  author =	{Chang, Evan and Kolhe, Neel and Sohn, Youngtak},
  title =	{{Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{47:1--47:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.47},
  URN =		{urn:nbn:de:0030-drops-210402},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.47},
  annote =	{Keywords: Random constraint satisfaction problem, replica symmetry breaking, interpolation bound}
}

Search Results

Documents authored by Chang, Evan

Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3

Abstract

Cite as

Thanks for your feedback!

Could not send message