Title: Specifying a positive threshold function via extremal points,
Abstract: An extremal point of a positive threshold Boolean function $f$ is either a
maximal zero or a minimal one. It is known that if $f$ depends on all its
variables, then the set of its extremal points completely specifies $f$ within
the universe of threshold functions. However, in some cases, $f$ can be
specified by a smaller set. The minimum number of points in such a set is the
specification number of $f$. It was shown in [S.-T. Hu. Threshold Logic, 1965]
that the specification number of a threshold function of $n$ variables is at
least $n+1$. In [M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying
Boolean functions by labelled examples. Discrete Applied Mathematics, 1995] it
was proved that this bound is attained for nested functions and conjectured
that for all other threshold functions the specification number is strictly
greater than $n+1$. In the present paper, we resolve this conjecture negatively
by exhibiting threshold Boolean functions of $n$ variables, which are
non-nested and for which the specification number is $n+1$. On the other hand,
we show that the set of extremal points satisfies the statement of the
conjecture, i.e., a positive threshold Boolean function depending on all its
$n$ variables has $n+1$ extremal points if and only if it is nested. To prove
this, we reveal an underlying structure of the set of extremal points.