论文标题
关于随机$ 3 $ regular Graphs的最小二分
On the minimum bisection of random $3$-regular graphs
论文作者
论文摘要
在本文中，我们在$ n $顶点上随机3型图的二级宽度提供了新的界限。主要的贡献是基于第一刻方法以及对图的结构分析的新下限$ 0.103295N $，从而改善了Kostochka和Melnikov的27岁结果。我们还通过将里昂的结果与原始组合见解相结合，给出了$ 0.139822N $的互补上限。进一步开发这种方法，我们在蒙特卡洛模拟的帮助下获得了不合格的改进上限。
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.
