The minimal order of a graph which is not an induced subgraph of the given graph. For example, the graph with two isolated vertices is not an induced subgraph of the complete graph on three vertices. By contrast, the minimal number of vertices of a graph which is not a subgraph of a graph is one plus the clique number [[St000097]].

The number of outer peaks of a permutation. An outer peak in a permutation $w = [w_1,..., w_n]$ is either a position $i$ such that $w_{i-1} < w_i > w_{i+1}$ or $1$ if $w_1 > w_2$ or $n$ if $w_{n} > w_{n-1}$. In other words, it is a peak in the word $[0,w_1,..., w_n,0]$.

The height of the tree associated to a permutation. A permutation can be mapped to a rooted tree with vertices $\{0,1,2,\ldots,n\}$ and root $0$ in the following way. Entries of the permutations are inserted one after the other, each child is larger than its parent and the children are in strict order from left to right. Details of the construction are found in [1]. The statistic is given by the height of this tree. See also [[St000325]] for the width of this tree.

The number of big descents of a permutation. For a permutation $\pi$, this is the number of indices $i$ such that $\pi(i)-\pi(i+1) > 1$. The generating functions of big descents is equal to the generating function of (normal) descents after sending a permutation from cycle to one-line notation [[Mp00090]], see [Theorem 2.5, 1]. For the number of small descents, see [[St000214]].

The number of cycle peaks and the number of cycle valleys of a permutation. A '''cycle peak''' of a permutation $\pi$ is an index $i$ such that $\pi^{-1}(i) < i > \pi(i)$. Analogously, a '''cycle valley''' is an index $i$ such that $\pi^{-1}(i) > i < \pi(i)$. Clearly, every cycle of $\pi$ contains as many peaks as valleys. See [2] for the exponential generating function, also see [3].

The genus of a permutation. The genus $g(\pi)$ of a permutation $\pi\in\mathfrak S_n$ is defined via the relation $$ n+1-2g(\pi) = z(\pi) + z(\pi^{-1} \zeta ), $$ where $\zeta = (1,2,\dots,n)$ is the long cycle and $z(\cdot)$ is the number of cycles in the permutation.

The holeyness of a permutation. For $S\subset [n]:=\{1,2,\dots,n\}$ let $\delta(S)$ be the number of elements $m\in S$ such that $m+1\notin S$. For a permutation $\pi$ of $[n]$ the holeyness of $\pi$ is $$\max_{S\subset [n]} (\delta(\pi(S))-\delta(S)).$$

The number of inner valleys of a permutation. The number of valleys including the boundary is [[St000099]].

The normalized sum of the minimal distances to a greater element. Set $\pi_0 = \pi_{n+1} = n+1$, then this statistic is $$ \sum_{i=1}^n \min_d(\pi_{i-1-d}>\pi_i\text{ or }\pi_{i+1+d}>\pi_i) $$ A closely related statistic appears in [1]. The generating function for the sequence of maximal values attained on $\mathfrak S_r$, $r\geq 0$ apparently satisfies the functional equation $$ (x-1)^2 (x+1)^3 f(x^2) - (x-1)^2 (x+1) f(x) + x^3 = 0. $$

The balance of a binary word. The balance of a word is the smallest number $q$ such that the word is $q$-balanced [1]. A binary word $w$ is $q$-balanced if for any two factors $u$, $v$ of $w$ of the same length, the difference between the number of ones in $u$ and $v$ is at most $q$.