(Dis)assortative partitions on random regular graphs

DOI10.1088/1751-8121/AC8B46OpenAlexW4292395792MaRDI QIDQ5877003FDOQ5877003

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 graphscavity methodmessage passing algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• On perfectly friendly bisections of random graphs
• Counting and hardness-of-finding fixed points in cellular automata on random graphs
• Partitioning problems via random processes
• Combinatorics. Abstracts from the workshop held January 1--7, 2023

This page was built for publication: (Dis)assortative partitions on random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5877003)