Premium
Optimization on sparse random hypergraphs and spin glasses
Author(s) -
Sen Subhabrata
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20774
Subject(s) - combinatorics , mathematics , limit (mathematics) , random graph , gaussian , degree (music) , block (permutation group theory) , discrete mathematics , value (mathematics) , optimization problem , stochastic block model , mathematical optimization , graph , statistics , physics , mathematical analysis , quantum mechanics , cluster analysis , acoustics
We establish that in the large degree limit, the value of certain optimization problems on sparse random hypergraphs is determined by an appropriate Gaussian optimization problem. This approach was initiated in Dembo et al. (2016) for extremal cuts of graphs. The usefulness of this technique is further illustrated by deriving the optimal value for Max q ‐cut on graphs, Max XORSAT on Erdős–Rényi hypergraphs, and the min‐bisection the min‐bisection for the Stochastic Block Model.