  The purpose of this article is to show that even the most elementary problems
in asymptotic extremal graph theory can be highly non-trivial. We study linear
inequalities between graph homomorphism densities. In the language of quantum
graphs the validity of such an inequality is equivalent to the positivity of a
corresponding quantum graph. Similar to the setting of polynomials, a quantum
graph that can be represented as a sum of squares of labeled quantum graphs is
necessarily positive. Lov\'asz asks whether the opposite is also true. We
answer this question and also a related question of Razborov in the negative by
introducing explicit valid inequalities that do not satisfy the required
conditions. Our solution to these problems is based on a reduction from real
multivariate polynomials and uses the fact that there are positive polynomials
that cannot be expressed as sums of squares of polynomials.
  It is known that the problem of determining whether a multivariate polynomial
is positive is decidable. Hence it is very natural to ask "Is the problem of
determining the validity of a linear inequality between homomorphism densities
decidable?" We give a negative answer to this question which shows that such
inequalities are inherently difficult in their full generality. Furthermore we
deduce from this fact that the analogue of Artin's solution to Hilbert's
seventeenth problem does not hold in the setting of quantum graphs.
