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:$b \leq f( n, m, k )$ for any $k$-uniform hypergraph $H$ having $n$ vertices and $m$ hyperedges.$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)$?
Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges
graph theory;co.combinatorics