Stability function

Stability function --- функция независимости.

The function [math]\displaystyle{ \alpha_{G}: \{0,1\}^{n} \rightarrow N }[/math] such that for each [math]\displaystyle{ x \in \{0,1\}^{n} }[/math] [math]\displaystyle{ \alpha_{G}(x) }[/math] is the stability number of a subgraph induced by [math]\displaystyle{ x }[/math]. It can be shown that this function can be expressed uniquely in the form

[math]\displaystyle{ \sum_{t \in \Delta}a_{t} \prod_{i \in t}x_{i}, }[/math]

where [math]\displaystyle{ \Delta }[/math] is a collection of subsets of [math]\displaystyle{ \{1, \ldots, n\} }[/math] and the [math]\displaystyle{ a_{t} }[/math]'s are real coefficients. This expression is called the polynomial expression of the stability function.