On perfectly friendly bisections of random graphs (Q6634425)

The paper under review is basically concerned with partitioning the vertex sets of Erdős-Rényi random graphs \(G(n,1/2)\) into two equal parts such that each vertex has more neighbours in its own part rather than in the other part. For example, a consequence of the main results in the paper is that there is a constant \(\gamma\simeq 0.17566\) (given by an analytical formula) such that, given \(\epsilon>0\) the following statement holds whp (i.e. with probability tending to 1 as \(n\rightarrow\infty\)). The statement is that \(G=G(n,1/2)\) has an equipartition (i.e. the two vertex classes of the partition have sizes within one of each other) such that every vertex in one class has at least \((\gamma-\epsilon)\sqrt{n}\) more neighbours in its own class than in the other class. Further, again whp, there is no equipartition such that every vertex has at least \((\gamma + \epsilon)\sqrt{n}\) more neighbours in its own class than in the other. This result actually follows from another result which involves careful computation of a key constant. In language used by some earlier papers on which this is an improvement, the authors prove the existence of a fully-friendly bisection. Mention should be made of concurrent work of \textit{Y. Dandi} et al. [``Maximally-stable local optima in random graphs and spin glasses: phase transitions and universality'', Preprint, \url{arXiv:2305.03591}] which established a similar result but not for all vertices -- a small set of \(o(n)\) exceptional vertices was allowed.\N\NThe basic idea is to look at the first and second moments of the number of bisections. By understanding these, the Paley-Zygmund theorem implies there is a strictly positive probability of such a bisection existing. However, we need to upgrade this from strictly positive probability to probability \(1-o(1)\). The impressive range of techniques thrown at the problem includes a key isoperimetric inequality which is established through an iterative application of Talagrand's inequality. The second moment method calculation uses ideas about Gaussian approximation to binomials from [\textit{O. Riordan} and \textit{A. Selby}, Comb. Probab. Comput. 9, No. 6, 549--572 (2000; Zbl 0971.05101)] and developed thereafter by \textit{B. McKay} and \textit{N. C. Wormald} [Random Struct. Algorithms 11, No. 2, 97--117 (1997; Zbl 0884.05081)] (and others). For the purposes of this paper, ideas from [McKay and Wormald, loc. cit.] have to be modified non-trivially to handle exponentially rare events. Even the resulting problem of finding some three and ten dimensional Gaussian integrals is not trivial to solve.\N\NThe authors note that their results have applications elsewhere, e.g. to the threshold for the symmetric perceptron (defined in the paper). They also pose the question of whether there is a polynomial-time algorithm to calculate a partition of \(G(n,1/2)\) into two parts in which every vertex has at least \(\delta \sqrt{n}\) more neighbours in its own part than in the other part for \(\delta>0\): there is some circumstantial evidence that this may be hard.