# Motivation behind the definition of order-$k$ (edge) expansion?

I'm trying to understand the motivation behind the idea of order-$$k$$ (edge) expansion for partitions of a graph, defined below:

For simplicity, let's focus on $$d$$-regular graphs. The definitions I'm working with are:

The edge expansion of a subset of vertices $$S$$ is $$\phi(S) = \frac{E(S,V \setminus S)}{d \cdot |S|},$$ where $$E(A,B)$$ counts the number of edges with one endpoint in $$A$$ and the other in $$B$$.

Let $$S_1, \ldots, S_k$$ collection of disjoint vertices, then their order-$$k$$ expansion is $$\phi_k(S_1, \ldots, S_k) = \max_{i=1,\ldots, k} \phi(S_i).$$ The order-$$k$$ expansion of a graph $$G$$ is $$\phi_k(G) = \min_{S_1, \ldots, S_k \text{ disjoint} } \phi(S_1, \ldots, S_k).$$

My question is: why do we consider the $$\max$$ in the definition of $$\phi_k(S_1, \ldots, S_k)$$? If $$S_j$$ is the subset of vertices for which $$\phi(S_i)$$ is a maximum, this means there are "a lot" of edges from $$S_j$$ to $$V \setminus S_j$$, relative to $$d|S_j|$$. Isn't the $$\min$$ more interesting here? Doesn't the $$\min$$ correspond to $$S_k$$ that can easily be removed from the graph (few edges need to be cut), and yet the subgraph being removed is relatively dense?

• Presumably the order $k$ expansion is related to the $k$th largest eigenvalue. – Yuval Filmus Mar 12 '19 at 9:21