1
$\begingroup$

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.

  • 0
    You are completely right - that's what I intended from the beginning. I've updated the question.2011-11-10

1 Answers 1

1

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$.

  • 0
    @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.2011-11-11