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?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .