Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

Question

This question was originally posted on mathoverflow. Having obtained no answers after one month, I've decided to cross-post it here.

---

Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n = |V|$ vertices and $m = |E|$ hyperedges. Let $O_w$ be the number of distinct edge induced subgraphs of $H$ having $w$ vertices and an odd number of hyperedges. Let $E_w$ be the number of distinct edge induced subgraphs of $H$ having $w$ vertices and an even number of hyperedges. Let $\Delta_w = O_w - E_w$.

Let $b_w$ be the number of bits required to encode $\Delta_w$, i.e. $b_w = log_2 \ \Delta_w$.

Let $b = \displaystyle\max_{\substack{w}} b_w$.

I'm interested in how $b$ grows. I would like to determine the best possible upper bound for $b$ which is expressible as a function of only $n$, $m$ and $k$. More precisely, I would like to determine a function $f(n,m,k)$ having both the following properties:

1. $b \leq f( n, m, k )$ for any $k$-uniform hypergraph $H$ having $n$ vertices and $m$ hyperedges.
2. $f(n,m,k)$ grows slower than any other function which satisfies the 1^st property.

In general both $O_w$ and $E_w$ are exponential in $m$, therefore I expect that their difference $\Delta_w$ is not exponential in $m$ and thus that $b \in o( m )$.

However for the moment I've no clue on how to try to prove this.

Questions

• How does $b$ grow with respect to $n$, $m$ and $k$?
• Are there any relevant results in the literature?
• Any hint on how to try to prove $b \in o(m)$?

Answer 1

It is the case that $b \notin o( m )$.

Let $G = ( V_G, E_G )$ be a $3$-regular connected graph. Without loss of generality, let us fix $w = |V_G|$ and focus on $\Delta_{|V_G|} = O_{|V_G|} - E_{|V_G|}$.

Pick an arbitrary edge $e = \{u, v\} \in E_G$. Remove $e$ and replace it with the following gadget:

This has the effect of multiplying $\Delta_{|V_G|}$ by $8$. The resulting graph $H = (V_H, E_H)$ is still $3$-regular connected, and has $60$ vertices more than $G$.

By repeating this process $i$ times, we obtain a $3$-regular connected graph having $|V_H| = |V_G| + 60i$ vertices, and whose $\Delta_{|V_H|}$ is $8^i$ times bigger than $\Delta_{|V_G|}$.

After $i = \frac{|V_G|}{3}$ iterations, our final graph will have $|V_H| = 21|V_G|$ vertices and a $\Delta_{|V_H|}$ which is $2^{|V_G|}$ times bigger than the $\Delta_{|V_G|}$ we started with. Let $n = |V_H|$, recall how $m = 1.5n$ for $3$-regular graphs, and we get a $\Delta_{|V_H|}$ whose absolute value is lower-bounded by $2^{\frac{m}{31.5}}$. Henceforth $b$ is linear in $m$ in the worst case, and thus it cannot belong to $o( m )$.

Contrarily to intuition (at least mine), the number of edge covers of odd cardinality and the number of edge covers of even cardinality may diverge by an exponential amount.