Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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