(Dis)assortative partitions on random regular graphs

DOI10.1088/1751-8121/AC8B46MaRDI QIDQ5877003zbMATH OpenOpenAlexFDO

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

Publication date 3 February 2023

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Maximum independent sets on random regular graphs
• Counting in two-spin models on \(d\)-regular graphs
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• Bipartitioning of directed and mixed random graphs

Cites work

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

Cited in

(8)

• Quenches in the Sherrington-Kirkpatrick model
• 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
• (Dis)assortative Partitions on Random Regular Graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• On marginal stability in low temperature spherical spin glasses

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)