<p>It is the case that $b \notin o( m )$.</p>

<p>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|}$.</p>

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

<p><a href="https://i.sstatic.net/oxmaL.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oxmaL.jpg" alt="Gadget"></a></p>

<p>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$. </p>

<p>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|}$. </p>

<p>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 )$.</p>

<p>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.</p>

CC BY-SA 3.0
2016-01-20T07:42:10.907Z
2016-01-20T07:42:10.907Z
Giorgio Camerani
<p>This question was originally posted on <a href="https://mathoverflow.net/questions/141516/bits-required-to-encode-difference-between-number-of-subgraphs-with-odd-number-o">mathoverflow</a>. Having obtained no answers after one month, I've decided to cross-post it here.</p>

<hr>

<p>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$.</p>

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

<p>Let $b = \displaystyle\max_{\substack{w}} b_w$.</p>

<p>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:</p>

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

<p>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 )$. </p>

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

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ul>
  <li>How does $b$ grow with respect to $n$, $m$ and $k$?</li>
  <li>Are there any relevant results in the literature?</li>
  <li>Any hint on how to try to prove $b \in o(m)$?</li>
  </ul>
</blockquote>

<graph-theory><co.combinatorics>
Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges
Giorgio Camerani
# Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

(Asked by: username_0 on 2013-10-09)

This question was originally posted on [mathoverflow](https://mathoverflow.net/questions/141516/bits-required-to-encode-difference-between-number-of-subgraphs-with-odd-number-o). 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 1st 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)$?

**Tags:** graph-theory, co.combinatorics


---

## 1 answers

### Answer by username_0 on 2016-01-20. Score: 1 | Accepted answer

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:

[![Gadget](https://i.sstatic.net/oxmaL.jpg)](https://i.sstatic.net/oxmaL.jpg)

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.


---

