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)$?
1 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.