  We prove that the optimal assignment kernel, proposed recently as an attempt
to embed labeled graphs and more generally tuples of basic data to a Hilbert
space, is in fact not always positive definite.
