2
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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.

$\endgroup$

Your Answer

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