English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For many random constraint satisfaction problems such as randomsatisfiability or random graph or hypergraph coloring, the best currentestimates of the threshold for the existence of solutions are based on thefirst and the second moment method. However, in most cases these techniques donot yield matching upper and lower bounds. Sophisticated but non-rigorousarguments from statistical mechanics have ascribed this discrepancy to theexistence of a phase transition called condensation that occurs shortly beforethe actual threshold for the existence of solutions and that affects thecombinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi,Semerjian, Zdeborova: PNAS 2007). In this paper we prove for the first timethat a condensation transition exists in a natural random CSP, namely in randomhypergraph 2-coloring. Perhaps surprisingly, we find that the second momentmethod breaks down strictly \emph{before} the condensation transition. Ourproof also yields slightly improved bounds on the threshold for randomhypergraph 2-colorability. We expect that our techniques can be extended toother, related problems such as random k-SAT or random graph k-coloring.

The condensation transition in random hypergraph 2-coloring