The last descent of a permutation. For a permutation $\pi$ of $\{1,\ldots,n\}$, this is the largest index $0 \leq i < n$ such that $\pi(i) > \pi(i+1)$ where one considers $\pi(0) = n+1$.

The degree of the graph. This is the maximal vertex degree of a graph.

The sum of the semi-lengths of tunnels before a valley of a Dyck path. For each valley $v$ in a Dyck path $D$ there is a corresponding tunnel, which is the factor $T_v = s_i\dots s_j$ of $D$ where $s_i$ is the step after the first intersection of $D$ with the line $y = ht(v)$ to the left of $s_j$. This statistic is $$ \sum_v (j_v-i_v)/2. $$

The number of positive eigenvalues of the Laplacian matrix of the graph. This is the number of vertices minus the number of connected components of the graph.

The treewidth of a graph. A graph has treewidth zero if and only if it has no edges. A connected graph has treewidth at most one if and only if it is a tree. A connected graph has treewidth at most two if and only if it is a series-parallel graph.

The spin of an integer partition. The Ferrers shape of an integer partition $\lambda$ can be decomposed into border strips. The spin is then defined to be the total number of crossings of border strips of $\lambda$ with the vertical lines in the Ferrers shape. The following example is taken from Appendix B in [1]: Let $\lambda = (5,5,4,4,2,1)$. Removing the border strips successively yields the sequence of partitions $$(5,5,4,4,2,1), (4,3,3,1), (2,2), (1), ().$$ The first strip $(5,5,4,4,2,1) \setminus (4,3,3,1)$ crosses $4$ times, the second strip $(4,3,3,1) \setminus (2,2)$ crosses $3$ times, the strip $(2,2) \setminus (1)$ crosses $1$ time, and the remaining strip $(1) \setminus ()$ does not cross. This yields the spin of $(5,5,4,4,2,1)$ to be $4+3+1 = 8$.

The dinv adjustment of an integer partition. The Ferrers shape of an integer partition $\lambda = (\lambda_1,\ldots,\lambda_k)$ can be decomposed into border strips. For $0 \leq j < \lambda_1$ let $n_j$ be the length of the border strip starting at $(\lambda_1-j,0)$. The dinv adjustment is then defined by $$\sum_{j:n_j > 0}(\lambda_1-1-j).$$ The following example is taken from Appendix B in [2]: Let $\lambda=(5,5,4,4,2,1)$. Removing the border strips successively yields the sequence of partitions $$(5,5,4,4,2,1),(4,3,3,1),(2,2),(1),(),$$ and we obtain $(n_0,\ldots,n_4) = (10,7,0,3,1)$. The dinv adjustment is thus $4+3+1+0 = 8$.

The size of a minimal vertex cover of a graph. A '''vertex cover''' of a graph $G$ is a subset $S$ of the vertices of $G$ such that each edge of $G$ contains at least one vertex of $S$. Finding a minimal vertex cover is an NP-hard optimization problem.

The largest eigenvalue of a graph if it is integral. If a graph is $d$-regular, then its largest eigenvalue equals $d$. One can show that the largest eigenvalue always lies between the average degree and the maximal degree. This statistic is undefined if the largest eigenvalue of the graph is not integral.

The pathwidth of a graph.