Upper bound on the number of induced subgraphs of the square lattice with all degrees even An induced subgraph of a graph $G$ is defined by a subset of vertices of $G$ together with all edges in $G$ that connect vertices from the chosen subset.
Consider now an $n\times m$ square lattice. Given a number $k$, how many choices of subsets of $k$ vertices are there such that the respective induced subgraphs have only vertices with an even number ($0$,$2$ or $4$) of adjacent edges? Notice that this includes single vertices without neighbours and that the subgraph is not necessarily connected.
I do not expect that there is a closed formula but an upper bound would be great. I am also thankful for links to similar problems.
 A: Focusing on the independent set question, ignoring the size $k$ question of independent sets at first, the asymptotic behavior of the number of independent sets in a $m\times n$ grid is described in this paper of Calkin and Wilf. The main result they show there is that if $f(m,n)$ is the number of independent sets on the grid graph on $m\times n$ vertices then $$\eta=\lim\limits_{m,n\rightarrow\infty} f(m,n)^{\frac{1}{mn}}$$ exists and satisfies $1.503047782 ... \leq \eta \leq 1.5035148...$, while numerically, the value $\eta=1.5030480824753323....$ seems to be correct.
Things are more complicated when the size constraint $k$ comes into play. There are some bounds for elements in the independence set sequence $i_{k}(G)$ (the number of independent sets in $G$ of size $k$) presented in this paper (Lemma 1.3). Letting $H(x) = −x \log x − (1 − x) \log(1 − x)$ be the binary entropy function, and $G$ be $d$-regular,
$$ i_k(G) ≤ \exp_{2}{\{ H(\frac{2k}{|V|})\frac{|V|}{2}+\frac{|V|}{2d} \}}$$
while for $G$ additionally bipartite
$$i_{k}(G)\geq \exp_{2}{\{H(\frac{2k}{|V|})\frac{|V|}{2}-\frac{1}{2}\log{|V|}\}}.$$
Incidentally, the independence sequence $i_k(G)$, for bipartite graphs $G$, is conjectured to be unimodal (Conjecture 1.2, in the second link above). Some results are known such as partial answers for regular bipartite graphs by D. Galvin. 
