An equipartition of a graph $G$ is a partition $V_1,...,V_k$ of its vertices to sets that are as equal as possible: $||V_i|-|V_j||\leq 1$.

We define the energy of the partition to be $q(\mathcal P)=\sum_{i,j} \frac {|V_i||V_j|}{n^2}d^2(V_i,V_j)$, where $d(X,Y):=\frac{e(X,Y)}{|X||Y|}$ is the density of the bipartite graph on $X$ and $Y$.

Let G be a graph of order $n$. let $\epsilon>0$ and let $\mathcal P = \{V_1,...,V_k,U_1,...,U_t\}$ be a partition of the vertices of $G$ with $|V1|=...=|V_k|$ and $\sum_i |U_i| \leq \epsilon n$.

Show that there is an equipartition $S=\{S_1,...,S_k\}$ of $G$ that satisfies $q(S) \geq q(P)-8\epsilon$.

We can assume $\epsilon < \frac18$ because $0<q(\cdot)<1$. (Since it is a weighted average of $d^2$ which is between $0$ and $1$.)

The constant $8$ is not optimal, and I think it can be replaced by $1$.

It is known that $q(\cdot )$ does not decrease when refining a partition, so it is enough to prove the claim when each of the $U_i$ is a single vertex. A natural way to form the new partition is to distribute the vertices equally and randomly, and to prove that such a random assignment works with positive probability. i.e. denoting $u=\sum |U_i|$ we add $\lfloor \frac uk \rfloor$ vertices to each of the $V_i$ and then add one vertex to each of the first $u \mod k$ sets $V_i$. An analysis of this method is not obvious because we need to control $d(S_i,S_j)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.