Computation via Substructures

Hilbert's Tenth problem asks if the existential fragment of natural number arithmetic is decidable. The DPRM theorem resolved this in the negative, but in doing so established a stronger result: the definable sets (i.e., the Diophantine Sets) are precisely the recursively enumerable sets of numbers. 

Recently, a surprising result of Halfon, Schnoebelen and Zetzsche showed that arithmetic is existentially definable in the subword order with constants, implying the undecidability of the corresponding existential fragment. This raises the natural question of whether the stronger result holds: is every recursively enumerable set of words existentially definable in the subword order with constants?

We present some initial results towards showing that the above conjecture is true and discuss the case of graphs and the induced subgraph order, for which coarser results were obtained in the speaker's PhD thesis.