Bounds on graph partitioning I am trying to find some generic upper bounds on the &quot;standard&quot; 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.
This is an area in which I'm not very familiar, but what you are looking for are so-called expander graphs.
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.