Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.756zbMath1375.68085arXiv1406.3617OpenAlexW2963646882MaRDI QIDQ5351933

Charilaos Efthymiou

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1406.3617

zbMATH Keywords

Galton-Watson treereconstruction problemrandom colouring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Coloring of graphs and hypergraphs (05C15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Phase transitions in discrete structures ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems ⋮ Local convergence of random graph colorings ⋮ Deterministic counting of graph colourings using sequences of subgraphs

This page was built for publication: Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees