Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs.

Florent Krzakała1, Andrea Pagnani, Martin Weigt

  • 1Dipartimento di Fisica, INFM and SMC, Università di Roma La Sapienza, P. A. Moro 2, I-00185 Roma, Italy.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|December 17, 2004
PubMed
Summary

This study validates the one-step replica symmetry breaking (1RSB) ansatz for graph coloring problems. It confirms 1RSB provides exact thresholds for colorability transitions in random graphs.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Streamlined optical training of large-scale modern deep learning architectures with direct feedback alignment.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same author

Controllable protein design via autoregressive direct coupling analysis conditioned on principal components.

PLoS computational biology·2026
Same author

Author Correction: Exploring the space of self-reproducing ribozymes using generative models.

Nature communications·2025
Same author

adabmDCA 2.0-A Flexible but Easy-to-Use Package for Direct Coupling Analysis.

Methods in molecular biology (Clifton, N.J.)·2025
Same author

Integrating experimental feedback improves generative models for biological sequences.

Nucleic acids research·2025
Same author

Exploring the space of self-reproducing ribozymes using generative models.

Nature communications·2025

Area of Science:

  • Graph Theory
  • Statistical Physics
  • Computational Complexity

Background:

  • Graph coloring is a fundamental problem in computer science and mathematics.
  • Previous studies utilized the cavity approach with the one-step replica symmetry breaking (1RSB) ansatz.
  • The validity of the 1RSB ansatz in this context required further rigorous examination.

Purpose of the Study:

  • To derive a general criterion for the validity of the 1RSB ansatz in graph coloring.
  • To determine exact threshold values for colorability transitions in Erdös-Rényi and regular random graphs.
  • To analyze the behavior of excited states and construct a global phase diagram.

Main Methods:

  • Derivation of a general validity criterion for the 1RSB ansatz.
  • Application of the criterion to the ground state of random graphs.

Related Experiment Videos

  • Analysis of asymptotic thresholds for large numbers of colors (q>>1).

    • Main Results:

    • A general criterion for the validity of the 1RSB ansatz was established.
    • The 1RSB solution was shown to yield exact threshold values, c(q), for colorability transitions.
    • Asymptotic thresholds for large q were found to be c(q) = 2q ln q - ln q - 1 + o(1), matching rigorous bounds.

    Conclusions:

    • The 1RSB ansatz is validated for determining exact colorability thresholds in random graphs.
    • The study provides precise asymptotic behavior for thresholds and characterizes excited states.
    • A comprehensive phase diagram for the graph coloring problem is presented.