Weighted Counting Formula and $2n/21$ Lower Bound for Induced Subgraphs with Prescribed Degree Parities

Abstract

Let $G=(V,E)$ be a finite simple graph of order $n\ge 1$, and let $\ell :V\to \{0,1\}$ be a prescribed parity labeling. A set $S\subseteq V$ is called $\ell$-admissible if $d_S(v)\equiv \ell (v)(\mathrm{mod}2)$ for every $v\in S$, where $d_S(v)=|N_G(v)\cap S|$. Let $h_{\ell }(G)$ be the maximum order of an $\ell$-admissible set and let $f_{\mathrm{oe}}(G)={\min }_{\ell }{h}_{\ell }(G)$. For $x\in \mathbb{R}$, define the weighted counting polynomial $$M_{\ell ,x}(G)=\sum _{S\in {\mathcal{A}}_{\ell }(G)}{x}^{|S|},$$ where ${\mathcal{A}}_{\ell }(G)$ is the collection of all $\ell$-admissible sets in $G$. For $R\subseteq V$, let $z_{\ell }(R)$ be the number of vertices $v\in V\setminus R$ for which $d_R(v)\equiv \ell (v)(\mathrm{mod}2)$. We prove the exact identity $$M_{\ell ,x}(G)=2^{-n}\sum _{R\subseteq V}{x}^{|R|}(2+x{)}^{z_{\ell }(R)}(2-x{)}^{n-z_{\ell }(R)-|R|}.$$ If $G$ has no isolated vertices, then, for every $\ell$ and every $x\in (0,2)$, $M_{\ell ,x}(G)>x^{n/2}(4-x^2{)}^{n/4}.$ Combining this estimate with a binary-entropy upper bound and optimizing $x$ gives $$f_{\mathrm{oe}}(G)>c_{\ast }n>\frac{2n}{21},$$ where $c_{\ast }\approx 0.095862615$. Ferber and Krivelevich (Adv. Math. 2022) proved that $h_1(G)\ge 10^{-4}n$, where $1$ is the all-one labeling. Since $h_1(G)\ge f_{\mathrm{oe}}(G)$, our result improves coefficient in their bound by almost three orders of magnitude, and does so simultaneously for every labeling.

6 pages