most recent 30 from http://mathoverflow.net 2013-05-25T20:17:54Z http://mathoverflow.net/feeds/question/85346 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85346/maximum-number-of-hyperedges-in-a-directed-hypergraph koeservat 2012-01-10T17:54:58Z 2012-01-10T20:06:00Z

<p>I need a formula for maximum number of hyperedges that a directed hypergraph with <em>n</em> vertices can have. Following point is an unresolved issues for me and it keeps coming back to my mind:</p> <ul> <li>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?</li> </ul>

http://mathoverflow.net/questions/85346/maximum-number-of-hyperedges-in-a-directed-hypergraph/85361#85361 Benjamin Young 2012-01-10T20:06:00Z 2012-01-10T20:06:00Z

<p>I doubt there's a completely standard definition. </p> <p>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)</p> <p>$\sum_{k=0}^n \binom{n}{k} 2^k = 3^n$</p> <p>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.</p>