On the minimum bisection of random 3-regular graphs

2020/09/01 by Lyuben Lichev, Lichev, Lyuben, Dieter Mitsche +1 · 1 citation
Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2009.00598

openalex publication_date 2020/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we give new bounds on the bisection width of random 3-regular graphs on n vertices. The main contribution is a new lower bound of 0.103295n based on a first moment method together with a structural analysis of the graph, thereby improving a 27-year-old result of Kostochka and Melnikov. We also give a complementary upper bound of 0.139822n by combining a result of Lyons with original combinatorial insights. Developping this approach further, we obtain a non-rigorous improved upper bound with the help of Monte Carlo simulations.

Cited by

• Bisection width, max-cut and internal partitions of 5-regular graphs

Related

• On Vertex Bisection Width of Random d-Regular Graphs
• Bisection width, max-cut and internal partitions of 5-regular graphs
• Random 4-regular graphs have 3-star decompositions asymptotically almost surely
• Friendly bisections of random graphs
• Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees