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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.