  Given an undirected graph $G$, the classical Cheeger constant, $h_G$,
measures the optimal partition of the vertices into 2 parts with relatively few
edges between them based upon the sizes of the parts. The well-known Cheeger's
inequality states that $2 \lambda_1 \le h_G \le \sqrt {2 \lambda_1}$ where
$\lambda_1$ is the minimum nontrivial eigenvalue of the normalized Laplacian
matrix.
  Recent work has generalized the concept of the Cheeger constant when
partitioning the vertices of a graph into $k > 2$ parts. While there are
several approaches, recent results have shown these higher-order Cheeger
constants to be tightly controlled by $\lambda_{k-1}$, the $(k-1)$-th
nontrivial eigenvalue, to within a quadratic factor.
  We present a new higher-order Cheeger inequality with several new
perspectives. First, we use an alternative higher-order Cheeger constant which
considers an "average case" approach. We show this measure is related to the
average of the first $k-1$ nontrivial eigenvalues of the normalized Laplacian
matrix. Further, using recent techniques, our results provide linear
inequalities using the $\infty$-norms of the corresponding eigenvectors.
Consequently, unlike previous results, this result is relevant even when
$\lambda_{k-1} \to 1$.
