2025/04/21 by Ma, Jie, Wu, Hehui
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.15096
In this paper, we investigate the problem of finding \it bisections (i.e., balanced bipartitions) in graphs. We prove the following two results for \it all graphs G: (1). G has a bisection where each vertex v has at least (1/4 - o(1))dG(v) neighbors in its own part; (2). G also has a bisection where each vertex v has at least (1/4 - o(1))dG(v) neighbors in the opposite part. These results are asymptotically optimal up to a factor of 1/2, aligning with what is expected from random constructions, and provide the first systematic understanding of bisections in general graphs under degree constraints. As a consequence, we establish for the first time the existence of a function f(k) such that for any k≥ 1, every graph with minimum degree at least f(k) admits a bisection where every vertex has at least k neighbors in its own part, as well as a bisection where every vertex has at least k neighbors in the opposite part. Using a more general setting, we further show that for any ε > 0, there exist cε, c'ε > 0 such that any graph G with minimum degree at least cε k (respectively, c'ε k) admits a bisection satisfying: every vertex has at least k neighbors in its own part (respectively, in the opposite part), and at least (1 - ε)|V(G)| vertices have at least k neighbors in the opposite part (respectively, in their own part). These results extend and strengthen classical graph partitioning theorems of Erdős, Thomassen, and Kühn-Osthus, while additionally satisfying the bisection requirement.