MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.