3
$\begingroup$

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 edge induced subgraphs of $H$ having $w$ vertices and an odd number of hyperedges. Let $E_w$ be the number of 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$. 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)$?

Update 13/09/2013
Here are some clarifications:

  • $O_w$ is the number of distinct edge-induced subgraphs in $H$. Repetitions are not allowed. The same holds for $E_w$ of course.
  • By "the number of bits required to encode $\Delta_w$" I mean $log_2 \ \Delta_w$.

Update 21/01/2016
This question has been answered on cstheory.

$\endgroup$
7
  • 1
    $\begingroup$ Can you explain what is meant by edge-induced? Especially, will the subgraphs be connected and k-uniform for large w? $\endgroup$ Sep 7, 2013 at 15:49
  • $\begingroup$ If the subgraphs are not k-uniform, looking at k-complete graphs should get b greater than 2n - logn. $\endgroup$ Sep 7, 2013 at 16:00
  • 1
    $\begingroup$ mathworld.wolfram.com/Edge-InducedSubgraph.html $\endgroup$ Sep 7, 2013 at 18:09
  • $\begingroup$ Of course every edge induced subgraph is $k$-uniform. $\endgroup$ Sep 7, 2013 at 18:26
  • 1
    $\begingroup$ Even so, complete hypergraphs should set the bar pretty high for b. $\endgroup$ Sep 7, 2013 at 19:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.