Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper resolves an open question by establishing a linear bound for graph connectivity partitioning, proving that a $641\ell$-connected graph $G$ admits a partition $V(G)=S\cup T$ where $G[S]$ and $G[T]$ are $\ell$-connected and the number of edges from $S$ to $T$ incident to any vertex in $S$ is at least $\ell$. This improves upon the previous quadratic bound of $2^{16}\ell^2$ established by K\"{u}hn and Osthus. The proof leverages the Moser-Tardos resampling algorithm to achieve this tighter bound.
A linear bound ($641\ell$) is proven for graph connectivity partitioning, resolving a long-standing open problem and improving upon a previous quadratic bound.
K\"{u}hn and Osthus proved that, for every positive integer $\ell$, every $2^{16}\ell^2$-connected graph $G$ has a partition $V(G)=S\cup T$ such that $G[S]$ and $G[T]$ are $\ell$-connected and $d_T(v)\geq \ell$ for every $v\in S$. And they asked whether the quadratic bound can be replaced by a linear bound. In this paper, we answer this question in the affirmative by proving that every $641\ell$-connected graph $G$ has a partition $V(G)=S\cup T$ such that $G[S]$ and $G[T]$ are $\ell$-connected and $d_T(v)\ge \ell$ for every $v\in S$. The proof integrates the Moser-Tardos resampling algorithm.