Proof that $\exp(-x^2) +\exp(-(x-y)^2)\leq 1 + 2\exp(-y^2)$ As stated in main text $$\exp(-x^2) +\exp(-(x-y)^2)\leq 1 + 2\exp(-y^2) ,\quad \forall x,y$$ with $0<x<y$, although it most likely also holds for all $x,y\in\mathbb{R}$.
The question came up in comparing effects of gaussian kernels. I've checked numerically for $x,y \in [0,10]$ and it always held. Local maxima of the left hand side is around $x = y\approx 1.9$.
The inequality is in a sense not tight, i.e. $\exists c<2$ with $\exp(-x^2) +\exp(-(x-y)^2)\leq 1 + c\exp(-y^2)$, however I've no idea what this $c$ would be (and I also don't need the tight version). But because it's not tight I gave up on most inequalities I know of such as all the AM-GM or Cauchy-Schwarz, because they're all tight in that sense.
 A: Let $w = x^2$ and $z = 2x (y - x)$.
We have $w, z > 0$ and $y = x + \frac{z}{2x}$.
The desired inequality is written as
$$\mathrm{e}^{-w} + \mathrm{e}^{-\frac{z^2}{4w}} \le 1 + 2\mathrm{e}^{-w - z - \frac{z^2}{4w}}. \tag{1}$$
We split into three cases.
Case 1: $z \ge 2$
Using $\mathrm{e}^{u} \ge 1 + u$ for all $u \ge 0$, we have
$$\mathrm{e}^{-w} + \mathrm{e}^{-\frac{z^2}{4w}}
\le \frac{1}{1 + w} + \frac{1}{1 + \frac{z^2}{4w} } \le \frac{1}{1 + w} + \frac{1}{1 + \frac{2^2}{4w} } = 1.$$
The desired result follows.
Case 2: $z \le \ln 2$
We have
$$1 + 2\mathrm{e}^{-w - z - \frac{z^2}{4w}}
\ge 1 + \mathrm{e}^{-w - \frac{z^2}{4w}}.$$
Also, we have
$$1 + \mathrm{e}^{-w - \frac{z^2}{4w}} - \mathrm{e}^{-w} - \mathrm{e}^{-\frac{z^2}{4w}}
= (1 - \mathrm{e}^{-w})(1 - \mathrm{e}^{-\frac{z^2}{4w}}) \ge 0.$$
The desired result follows.
Case 3: $\ln 2 < z < 2$
The desired inequality is written as
$$\mathrm{e}^{-w} + \mathrm{e}^{-\frac{z^2}{4w}}(1 - 2\mathrm{e}^{-w - z}) \le 1.$$
Using $\mathrm{e}^{-z} \ge (1 - z/4)^4 > 0$ (equivalently $\mathrm{e}^{-z/4} \ge 1 - z/4 > 0$), it suffices to prove that
$$\mathrm{e}^{-w} + \mathrm{e}^{-\frac{z^2}{4w}}\Big(1 - 2\mathrm{e}^{-w}(1 - z/4)^4\Big) \le 1.$$
Using $\mathrm{e}^{u} \ge 1 + u + \frac12 u^2$ for all $u \ge 0$, we have
$$\mathrm{e}^{-\frac{z^2}{4w}}
\le \frac{1}{1 + \frac{z^2}{4w} + \frac12(\frac{z^2}{4w})^2}.$$
It suffices to prove that
$$\mathrm{e}^{-w} + \frac{1}{1 + \frac{z^2}{4w} + \frac12(\frac{z^2}{4w})^2}\Big(1 - 2\mathrm{e}^{-w}(1 - z/4)^4\Big) \le 1$$
or
$$\left(1 - \frac{2(1 - z/4)^4}{1 + \frac{z^2}{4w} + \frac12(\frac{z^2}{4w})^2}\right) \mathrm{e}^{-w} + \frac{1}{1 + \frac{z^2}{4w} + \frac12(\frac{z^2}{4w})^2} \le 1.$$
Using $\mathrm{e}^{u} \ge 1 + u + \frac12 u^2$ for all $u \ge 0$, we have
$$\mathrm{e}^{-w} \le \frac{1}{1 + w + \frac12 w^2}.$$
It suffices to prove that
$$\left(1 - \frac{2(1 - z/4)^4}{1 + \frac{z^2}{4w} + \frac12(\frac{z^2}{4w})^2}\right) \frac{1}{1 + w + \frac12 w^2} + \frac{1}{1 + \frac{z^2}{4w} + \frac12(\frac{z^2}{4w})^2} \le 1$$
or (after clearing the denominators)
$$3wz^4 + 4z^2(2w - z)^2 + 128w(z - 1)^2 \ge 0$$
which is clearly true.
We are done.
A: More than likely, this is too complex.
If you consider that you want the minimum value of function
$$F(x,y)=1+2 e^{-y^2}-e^{-x^2}-e^{-(x-y)^2}\tag 1$$
$$\frac{\partial F(x,y)}{\partial x}=2 e^{-x^2} x+2 e^{-(x-y)^2} (x-y)\tag 2$$
$$\frac{\partial F(x,y)}{\partial y}=-2 e^{-(x-y)^2} (x-y)-4 e^{-y^2} y \tag 3$$ But $(3)$ makes thinking about Lambert function. Using it
$$\frac{\partial F(x,y)}{\partial y}=0 \implies x_\pm=y \pm \frac{1}{\sqrt{2}}\sqrt{-W\left(-8y^2 e^{-2 y^2} \right)}$$ But, since we have the restriction $x<y$
$$x=x_*=y - \frac{1}{\sqrt{2}}\sqrt{-W\left(-8y^2 e^{-2 y^2} \right)}\tag 4$$ which, in the real domain, is positive and defined if
$$-8y^2 e^{-2 y^2} \geq -\frac 1e \implies y \geq  \sqrt{-\frac 12 W_{-1}\left(-\frac{1}{4 e}\right) }=1.35879$$ where now appears the second branch of Lambert function.
Plugging $(4)$ in $(1)$
$$F(x_*,y)=e^{-y^2} \left(e^{y^2}+2-e^{\frac{1}{2} W\left(-8y^2 e^{-2 y^2} \right)} \left(e^{y^2}+e^{\sqrt{2}
   y \sqrt{-W\left(-8y^2 e^{-2 y^2} \right)}}\right)\right)\tag 5$$ which always positive (have a look here for the plot).
Notice that $e^{\frac{1}{2} W\left(-8y^2 e^{-2 y^2} \right)}$ is basically $1-\epsilon$; for $y=2$, it is $0.994589$ and for $y=3$, it is $0.999999$.
This means that
$$F(x_*,y) > e^{-y^2} \left(2-e^{\sqrt{2} y \sqrt{-W\left(-8 e^{-2 y^2} y^2\right)}}\right)$$
