Bounds on graph partitioning
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.