0
$\begingroup$

I need a formula for maximum number of hyperedges that a directed hypergraph with n vertices can have. Following point is an unresolved issues for me and it keeps coming back to my mind:

  • There are different definitions for hyperedges in directed hypergraphs (e.g. some say a hyperedge e = (T(e), H(e)) in which T(e) and H(e) cannot be empty set, some say they H(e) can be empty set). Is there a standart definition I'm missing?
$\endgroup$
0
$\begingroup$

I doubt there's a completely standard definition.

It seems like this is elementary -- an undirected edge is a size-$k$ subset of $[1,n]$, and a directed edge is an undirected edge together with one of the possible $2^k$ labellings of it with "T" and "H". So the number of different edges is (if, say, empty head- and tail-sets are allowed)

$\sum_{k=0}^n \binom{n}{k} 2^k = 3^n$

Presumably a directed hypergraph consists of any collection of such edges, so there are $2^{3^n}$ of them. If this isn't the precise question you were wondering about, I'd wager that the one you're interested in is just as easy to count.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.