Perfectly balanced partitions of smoothed graphs

Ido Ben-Eliezer ; Michael Krivelevich

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

For a graph $G=(V,E)$ of even order, a partition $(V_1,V_2)$ of the vertices is said to be perfectly balanced if $|V_1|=|V_2|$ and the numbers of edges in the subgraphs induced by $V_1$ and $V_2$ are equal. For a base graph $H$ define a random graph $G(H,p)$ by turning every non-edge of $H$ into an edge and every edge of $H$ into a non-edge independently with probability $p$. We show that for any constant $\epsilon$ there is a constant $\alpha$, such that for any even $n$ and a graph $H$ on $n$ vertices that satisfies $\Delta(H)-\delta(H) \leq \alpha n$, a graph $G$ distributed according to $G(H,p)$, with ${\epsilon\over n} \leq p \leq 1-{\epsilon\over n}$, admits a perfectly balanced partition with probability exponentially close to $1$. As a direct consequence we get that for every $p$, a random graph from $G(n,p)$ admits a perfectly balanced partition with probability tending to $1$.

Détail

DOI : 10.37236/252

Classification : 05C80, 05C70