Friendly bisections of random graphs

DOI10.1090/CAMS/13MaRDI QIDQ6052387zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Matthew Kwan, Bhargav P. Narayanan, Ashwin Sah, Mehtaab Sawhney

Publication date 17 October 2023

Published in Communications of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.13337

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: Resolving a conjecture of F"uredi from 1988, we prove that with high probability, the random graph $G(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which $n-o(n)$ vertices have at least as many neighbours in their own part as across. The engine of our proof is a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument.

Recommendations

• Bisecting sparse random graphs
• A spectral heuristic for bisecting random graphs
• scientific article; zbMATH DE number 2019629
• Bisections of graphs
• Bipartite decomposition of random graphs

Cites work

• A complete proof of universal inequalities for the distribution function of the binomial law
• Algorithmic approach to the satisfactory graph partitioning problem
• An estimate of the remainder in a combinatorial central limit theorem
• Anticoncentration for subgraph statistics
• Anticoncentration versus the Number of Subset Sums
• 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 given degree sequence
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• Graph decomposition with constraints on the connectivity and minimum degree
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 4191687 (Why is no real title available?)
• scientific article; zbMATH DE number 5652361 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1933255 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 6319745 (Why is no real title available?)
• Internal partitions of regular graphs
• Local max-cut in smoothed polynomial time
• Local minima in disordered mean-field ferromagnets
• Local optima of the Sherrington-Kirkpatrick Hamiltonian
• On a packing and covering problem
• On the max-cut of sparse random graphs
• Problems and results on judicious partitions
• Random triangle removal
• Singularity of sparse random matrices: simple proofs
• Smoothed complexity of local max-cut and binary max-CSP
• The early evolution of the \(H\)-free process
• The number of graphs and a random graph with a given degree sequence
• The probabilistic method
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Unfriendly partitions of a graph
• Zero-temperature dynamics in the dilute Curie-Weiss model

Cited in

(6)

• Bisecting sparse random graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• A note on internal partitions: the 5-regular case and beyond
• On perfectly friendly bisections of random graphs
• Partitioning problems via random processes
• Majority dynamics: the power of one

This page was built for publication: Friendly bisections of random graphs

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