Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

The condensation transition in random hypergraph 2-coloring

Tools
- Tools
+ Tools

Coja-Oghlan, Amin and Zdeborová, Lenka (2012) The condensation transition in random hypergraph 2-coloring. In: ACM-SIAM Symposium on Discrete Algorithms 2012, Kyoto, Japan, 17-19 Jan 2012. Published in: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms pp. 241-250. ISSN 1557-9468.

Research output not available from this repository, contact author.
Official URL: http://siam.omnibooksonline.com/2012SODA/data/pape...

Request Changes to record.

Abstract

For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborová: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. Copyright © SIAM.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science > Computer Science
Faculty of Science > Mathematics
Journal or Publication Title: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher: SIAM
ISSN: 1557-9468
Official Date: 17 January 2012
Dates:
DateEvent
17 January 2012Published
Page Range: pp. 241-250
Status: Not Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
Conference Paper Type: Paper
Title of Event: ACM-SIAM Symposium on Discrete Algorithms 2012
Type of Event: Conference
Location of Event: Kyoto, Japan
Date(s) of Event: 17-19 Jan 2012
Related URLs:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us