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.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 16 '18 at 19:51
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy