On the minimum bisection of random 3-regular graphs (Q6106297)
From MaRDI portal
scientific article; zbMATH DE number 7702596
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the minimum bisection of random 3-regular graphs |
scientific article; zbMATH DE number 7702596 |
Statements
On the minimum bisection of random 3-regular graphs (English)
0 references
27 June 2023
0 references
Summary: 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 \textit{A. V. Kostochka} and \textit{L. S. Melnikov} [in: Вероятностные методы дискретной\ математики. Труды третьей\ Петрозаводской\ конференции. Петрозаводск (Россия), 11--16 мая 1992 г. Moskva: TVP; Utrecht: VSP. 251--265 (1993; Zbl 0811.05035)]. 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.
0 references
lower bound
0 references
cubic graphs
0 references
cubic simple graph
0 references
isoperimetric number
0 references
0 references
