(Dis)assortative partitions on random regular graphs

DOI10.1088/1751-8121/ac8b46OpenAlexW4292395792MaRDI QIDQ5877003

Gabriel Arpino, Yaroslav Kivva, Freya Behrens, Lenka Zdeborová

Publication date: 3 February 2023

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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

zbMATH Keywords

partitionsphase transitionsdisordered systemsrandom graphsmessage passing algorithmscavity method

Mathematics Subject Classification ID

Computer science (68-XX) Statistical mechanics, structure of matter (82-XX)

Related Items

Combinatorics. Abstracts from the workshop held January 1--7, 2023, Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023

Cites Work

• Satisfactory graph partition, variants, and generalizations
• Algorithmic approach to the satisfactory graph partitioning problem
• Short cycles in random regular graphs
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• The marginally stable Bethe lattice spin glass revisited
• Extremal cuts of sparse random graphs
• Suboptimality of local algorithms for a class of max-cut problems
• On a conjecture of Schweser and Stiebitz
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Simple Local Search Problems that are Hard to Solve
• Expander graphs and their applications
• Information, Physics, and Computation
• Metastable states in asymmetrically diluted Hopfield networks
• On the max‐cut of sparse random graphs
• Contagion
• Random multi-index matching problems
• Storage capacity in symmetric binary perceptrons
• Algorithms and Computation
• Neural networks and physical systems with emergent collective computational abilities.
• Decomposing C₄‐free graphs under degree constraints
• Frozen 1-RSB structure of the symmetric Ising perceptron
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item