# Bounds on graph partitioning

I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $$|V|$$ vertices and $$|E|$$ edges I want to partition it into two equal $$N/2$$ (or approximately equal if easier) parts while minimizing the cut i.e. $$\min(|C|)$$ where $$C$$ is the set of edges with nodes on either side of the partition (similarly nodes that the cut goes through).

So far this is standard stuff and clearly the optimal solution depends on the details of the graph. However, what I want is an upper bound on $$\min(|C|)$$ in terms of $$|V|$$ and $$|E|$$ without knowing anything else about the graph. If no upper bound then even some type of average case estimate would help.

Also, the same thing for a multigraph.

• What is the answer for the complete graph $K_n$ on $n$ vertices? You may assume $n$ is even. Apr 9, 2021 at 13:09
• Do you think that you could get a bigger cut than that for a simple graph? Apr 9, 2021 at 14:35
• @PålGD The complete graph has a fixed structure (I know what the graph looks like) and so it is easy to find an exact solution ($n^2/4$). However what If I say for example $|E|=|V|=n$ ? Will the worst case solution be 2, as in the case where the graph is a polygon ? Apr 9, 2021 at 14:43
• Okay, so let $|E| = |V| = n$ and let $G \supseteq K_\sqrt{n}$. Apr 9, 2021 at 14:55
• If I understand you correctly the answer for this subset of cases is 0 since less than n/2 of the vertices have edges. So I just put all the edges in one partition. But I already know of a case (my comment above) where the answer is 2 so the upper bound is at least 2. Apr 9, 2021 at 15:04

A graph $$G$$ has edge expansion $$h(G) = \min_{0 \leq |S| \leq \frac n 2} \frac{|\partial S|}{|S|},$$ where $$\partial S$$ is the boundary of $$S$$, i.e., the edges with exactly one endpoint in $$S$$.
This isn't exactly what you ask for, but you can also consider only $$S$$ of size exactly $$\frac n 2$$. There are $$d$$-regular expander graph classes. Perhaps that will point you towards something.