On perfectly friendly bisections of random graphs

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean functions (06E30)

Cites Work

Unnamed Item
Unnamed Item
A structure theorem for Boolean functions with small total influences
Satisfactory graph partition, variants, and generalizations
The distribution of the maximum degree of a random graph
Algorithmic approach to the satisfactory graph partitioning problem
Asymptotic enumeration by degree sequence of graphs of high degree
Local algorithms for independent sets are half-optimal
Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
Discrete variants of Brunn-Minkowski type inequalities
Sharp threshold for the Ising perceptron model
Concentration on the Boolean hypercube via pathwise stochastic analysis
Suboptimality of local algorithms for a class of max-cut problems
Asymptotic enumeration of dense 0-1 matrices with specified line sums
Central and local limit theorems applied to asymptotic enumeration
The Maximum Degree of a Random Graph
Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
Asymptotic Enumeration of Graphs with a Given Upper Bound on the Maximum Degree
On the Increase of Dispersion of Sums of Independent Random Variables
Metastable states in asymmetrically diluted Hopfield networks
Sharp thresholds of graph properties, and the $k$-sat problem
The degree sequence of a random graph. I. The models
On the max‐cut of sparse random graphs
Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic
High-Dimensional Probability
Every monotone graph property has a sharp threshold
Storage capacity in symmetric binary perceptrons
(Dis)assortative partitions on random regular graphs
Limits of local algorithms over sparse random graphs
Noise sensitivity of Boolean functions and applications to percolation
Degree sequences of random digraphs and bipartite graphs
Friendly bisections of random graphs
Frozen 1-RSB structure of the symmetric Ising perceptron
Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
Subgraph distributions in dense random regular graphs
Sharp threshold sequence and universality for Ising perceptron models

This page was built for publication: On perfectly friendly bisections of random graphs