We define a partition of an undirected graph $G=(V, E)$ as some set $A \subseteq V$, which partitions $V$ into $A$ and $V \setminus A = B$. Define $n=|V|$. We call a partition $\alpha$-balanced if $\alpha \cdot n \leq |A| \leq (1-\alpha) \cdot n$ for some fixed constant $\alpha$ ($0 < \alpha \leq 1/2$), so $A$ and $B$ both contain at least some constant fraction of $V$. We define the imbalance between $A$ and $B$ as $||A|-|B||$ (so as the absolute difference between their sizes).

We call a partition $c$-crossing if $ \# \{(a,b) \in E | (a \in A, b \in B) \vee (a \in B, b \in A)\} \leq c$ for some constant $c$, so if the number of edges not completely inside $A$ or $B$ is at most a constant.

We call a graph $k$-bounded if every vertex has degree at most $k$.

I conjecture that there exist fixed $\alpha$ and $c$ such that any 3-bounded graph has a $c$-crossing $\alpha$-balanced partition.

Any 2-bounded graph has a $2$-crossing $1/4$-balanced partition: consider the connected components of such a graph. Starting from small to large, we assign these components to either $A$ or $B$ in their entirety, picking the set with the least vertices (so far) out of $A$ and $B$. Because we go from small to large, we will end up alternating between $A$ and $B$, and this means that the imbalance between $|A|$ and $|B|$ will at most be the size of the largest connected component.

The graph is 2-bounded, so all connected components are cycles, lines or single points. If the largest connected component is a point, the imbalance is 1 and we have a $2$-crossing $1/4$-balanced partition. Otherwise, it is a cycle or line and we can cut it in half, assigning one half to $A$ and the other to $B$. This halves the imbalance, and since the imbalance of $A$ and $B$ is at most $n$, the resulting imbalance is at most $n/2$, so $\alpha = 1/4$ will work. Cutting it in half only gives us 2 edges crossing the partition, so $c=2$ will work as well.

Does the same thing work for 3-bounded graphs as well? It seems like we only have to be able to cut a connected component in half for this to work. Bonus points if you can give a fast algorithm for finding such a partition.

I've tried searching on the subject, but I've found nothing. I might just be searching for the wrong things though. The motivation for the subject is from Computer Science: this is a subproblem of a problem I'm trying to find a good algorithm for.

  • $\begingroup$ The definitions seem a bit confused to me. From the way you use them later in the question, it seems to me that they're not actually meant to apply to individual graphs (in which case you'd have to specify $\alpha$ and $c$ up front), but to classes of graphs; i.e. it seems that what you had in mind was more like "a class of graphs allows good balanced partitions if there are $\alpha$ and $c$ such that for all graphs in the class ..."? (Also you'd probably want $\alpha\gt0$.) $\endgroup$ – joriki Nov 10 '11 at 23:34
  • $\begingroup$ You are completely right - that's what I intended from the beginning. I've updated the question. $\endgroup$ – Alex ten Brink Nov 10 '11 at 23:43

I believe your conjecture might be false, unfortunately.

Existence of 3-regular expander graphs would disprove your conjecture.

Expander graphs have the property that any subset of vertices have a sufficient fraction of neighbours.

For a good discussion, see Terry Tao's blog post: http://terrytao.wordpress.com/2008/01/11/distinguished-lecture-series-ii-avi-wigderson-expander-graphs-constructions-and-applications/

I found this paper which references another paper (Mark S. Pinsker. On the complexity of a concentrator. In 7th Annual Teletraffic Conference, pages 318/1–318/4, Stockholm, 1973.), which claims almost all $d$-regular graphs are expander graphs for $d \ge 3$.

  • $\begingroup$ That said, you might get better information at cstheory.stackexchange.com. $\endgroup$ – Aryabhata Nov 11 '11 at 21:06
  • $\begingroup$ The claim you mention is also in Terry Tao's blog post. Fixing d=3, this means that there is at least one (and apparently many) expander family which won't be partitionable as I describe, which answers my question. Thanks for the help - I'll have to look for a different approach now. $\endgroup$ – Alex ten Brink Nov 11 '11 at 21:38
  • $\begingroup$ I wasn't sure whether to post this here or on cstheory - graph problems aren't exactly exclusive to computer science, so I thought it might have been off-topic there. $\endgroup$ – Alex ten Brink Nov 11 '11 at 21:39
  • $\begingroup$ @AlextenBrink: The reason I suggested cstheory was because of the experts who visit there. Note that, even though cstheory is for research level questions (and not just any CS questions), it does look like the question you have would be welcome there. $\endgroup$ – Aryabhata Nov 11 '11 at 21:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.