Shotgun reconstruction in the hypercube

DOI10.1002/rsa.21028zbMath1522.05139arXiv1907.07250OpenAlexW3174451973MaRDI QIDQ6074678

Alexander D. Scott, Michał Przykucki, Alexander Roberts

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random coloringsshotgun reconstructionvertex-isoperimetric stability

Mathematics Subject Classification ID

Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Shotgun assembly threshold for lattice labeling model ⋮ Vertex-isoperimetric stability in the hypercube

Cites Work

• A congruence theorem for trees
• Combinatorial reconstruction problems
• Ergodic properties of color records
• Reconstructing subsets of \(\mathbb{Z}_n\)
• The combinatorial \(k\)-deck
• Stability for vertex isoperimetry in the cube
• Vertex-isoperimetric stability in the hypercube
• Locally biased partitions of \(\mathbb{Z}^n\)
• Distinguishing sceneries by observing the scenery along a random walk path
• Topics in Graph Automorphisms and Reconstruction
• Almost every graph has reconstruction number three
• Finite Subsets of the Plane are 18-Reconstructible
• Shotgun assembly of random jigsaw puzzles
• Indistinguishable Sceneries on the Boolean Hypercube
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Unique reconstruction threshold for random jigsaw puzzles
• Optimal numberings and isoperimetric problems on graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item