# 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.

• For small k, a lot of them (probably the bulk) will be k isolated points. I would not be surprised if a good upper bound was twice this number. Gerhard "Going For The Rough Guess" Paseman, 2018.11.16. – Gerhard Paseman Nov 16 '18 at 19:51
• If $k=o(\sqrt{mn})$ then $k$ vertices chosen at random will be an independent set with probability close to 1, so the number of cases will be close to $\binom{mn}{k}$. Probabilistic reasoning could handle somewhat larger $k$, but the general case seems more difficult. – Brendan McKay Nov 17 '18 at 3:41

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.