On perfectly friendly bisections of random graphs
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. The 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. The 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.
- (Dis)assortative partitions on random regular graphs
- A structure theorem for Boolean functions with small total influences
- Algorithmic approach to the satisfactory graph partitioning problem
- Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotic Enumeration of Graphs with a Given Upper Bound on the Maximum Degree
- Central and local limit theorems applied to asymptotic enumeration
- Concentration on the Boolean hypercube via pathwise stochastic analysis
- Degree sequences of random digraphs and bipartite graphs
- Discrete variants of Brunn-Minkowski type inequalities
- Every monotone graph property has a sharp threshold
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Friendly bisections of random graphs
- Frozen 1-RSB structure of the symmetric Ising perceptron
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 3373547 (Why is no real title available?)
- scientific article; zbMATH DE number 3387680 (Why is no real title available?)
- Limits of local algorithms over sparse random graphs
- Local algorithms for independent sets are half-optimal
- Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
- Metastable states in asymmetrically diluted Hopfield networks
- Noise sensitivity of Boolean functions and applications to percolation
- On the Increase of Dispersion of Sums of Independent Random Variables
- On the max-cut of sparse random graphs
- Performance of sequential local algorithms for the random NAE-K-SAT problem
- Satisfactory graph partition, variants, and generalizations
- Sharp threshold for the Ising perceptron model
- Sharp threshold sequence and universality for Ising perceptron models
- Sharp thresholds of graph properties, and the k-sat problem
- Storage capacity in symmetric binary perceptrons
- Subgraph distributions in dense random regular graphs
- Suboptimality of local algorithms for a class of max-cut problems
- The degree sequence of a random graph. I. The models
- The distribution of the maximum degree of a random graph
- The maximum degree of a random graph
This page was built for publication: On perfectly friendly bisections of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6634425)
