Is there a gapless Hamiltonian whose gaplessness is stable against arbitrary perturbations? Does anyone know of a translation invariant lattice model (any dimension, bosonic or fermionic) which is gaplessness and remains so when adding arbitrary perturbations (if these are small enough), i.e. we do not enforce any symmetry. Note that Fermi surfaces don't do the job, since they require particle number conservation (i.e. a $U(1)$ symmetry).
Or is there a clear argument to exclude this possibility?
 A: The answer seems to be: yes.
For example, in an article by Hermele, Fisher and Balents (2003), they consider a $U(1)$ spin liquid in three dimensions where they concretely claim that ``[t]his state is stable to ALL zero-temperature perturbations''.
A generalization was studied more recently (for example) by Rasmussen, You and Xu (2016). In the introduction of that paper, they also give a nice list of references to other works which have considered stable gapless phases (in two and three dimensions).
(Sidenote: it would be interesting to prove such stable gapless phases are not possible in one dimension.)
EDIT: it turns out there are even examples in one spatial dimension! There are so-called 'perfect metals' which are stable against any perturbation (thanks to Ryan Thorngren for pointing this out to me). These require large central charge by virtue of Hellerman's theorem, which says there is always an operator with dimension $\Delta \lessapprox \frac{c}{6} + 0.473695$, hence, there is always a relevant operator if $c \lessapprox 9.13$.
A: What about Luttinger Liquids? They describe an universality class for nearest-neighbour-1D systems* (the canonical example is Hubbard Model, which remains gapless until the ratio hopping/repulsion~1)
*Actually, if I'm not mistaken, next-nearest-neighbour pertubations are not relevant for several models that belong to this U.C. (e.g. Ising (?))
