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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.