Bounds on Odd and Odd-Even Induced Subgraphs

Abstract

Let $G$ be an $n$-vertex graph and let $\ell :V(G)\to {\mathbb{F}}_2$ prescribe degree parities. A set $S\subseteq V(G)$ is $\ell$-admissible if every $v\in S$ has degree congruent to $\ell (v)$ modulo $2$ in $G[S]$. Let $h_{\ell }(G)$ be the maximum order of an $\ell$-admissible set, set $f_{\mathrm{oe}}(G):={\min }_{\ell }{h}_{\ell }(G)$, and write $f_o(G):=h_1(G)$, where $1(v)=1$ for every $v\in V(G).$ We prove three main results for graphs without isolated vertices. First, by extending Zeng's odd-cut method to arbitrary parity prescriptions an introducing a one-sided completion lemma, we show that $h_{\ell }(G)\ge n/6$ for every $\ell$. Consequently, $f_{\mathrm{oe}}(G)\ge n/6$, improving the previous bound $2n/21$. Second, for bipartite graphs we derive lower bounds on $f_o(G)$ in terms of the ${\mathbb{F}}_2$-rank of the bipartite adjacency matrix and combine them to obtain \[ f_o(G)\ge \left(\frac14+\frac1{256}\right)n=\frac{65}{256}n. \] Thus, in the bipartite case, the factor $2$ in Scott's bound $f_o(G)\ge n/(2\ddot{I}‡(G))$ can be replaced by $128/65<2$. Finally, writing $\hat{I}\pm =\hat{I}\pm (G)$, a fourth-moment argument gives, for $\hat{I}\pm \ge 2$, \[ f_o(G)\ge \fracα{2}+\frac{\log_3α}{8} -\frac14\log_3\log_3\sqrtα. \] We also construct bipartite graphs satisfying \[ f_o(G)\le \frac{α(G)}2+\log_2\!\bigl(α(G)+1\bigr)+\frac12, \] showing that the logarithmic additive improvement over Scott's bound $f_o(G)\ge \hat{I}\pm (G)/2$ has the optimal order of magnitude.