Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Undecidability of linear inequalities in graph homomorphism densities   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.

21
The categories of this paper are: adap-org
22
The categories of this paper are: chao-dyn
20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
15
The categories of this paper are: nucl-ex
35
The categories of this paper are: mtrl-th
4
The categories of this paper are: cond-mat
0
The categories of this paper are: hep-ph
10
The categories of this paper are: q-bio
13
The categories of this paper are: quant-ph
16
The categories of this paper are: stat
6
The categories of this paper are: astro-ph
18
The categories of this paper are: econ
1
The categories of this paper are: cs
27
The categories of this paper are: comp-gas
24
The categories of this paper are: dg-ga