From an [answer][1] to this [question][2] I have learned how to ask this question properly. Consider a [$k$-uniform hypergraph][3] on $n$ nodes, i.e. a family of $k$-subsets of $[n]= \{1,2,\dots,n\}$ (the hyperedges). Consider a sequence $\langle a_1, a_2, \dots a_n \rangle$ giving the numbers of hyperedges that node $i\in [n]$ is contained in. In the case of $k=2$ this is the classical degree sequence. So let me call the sequence a **[hyper-degree sequence][4]** when $k\leq n$ is arbitrary. It obviously holds that $a_i \leq \binom{n-1}{k-1}$. For $k=2$ we know by the [handshaking lemma][5] that $\sum_i a_i = 0 \text{ mod } 2$, and I assume that this holds for all $k$: $\sum_i a_i = 0 \text{ mod } k$. My question is fourfold: - What's the best known algorithm (probably not "efficient") to check if a given sequence $\langle a_1, a_2, \dots a_n \rangle$ with $a_i \leq \binom{n-1}{k-1}$ and $\sum_i a_i = 0 \text{ mod } k$ is the hyper-degree sequence of some $k$-uniform hypergraph on $n$ nodes? - Even though it may be hard to tell exactly how many of such sequences are hyper-degree sequences, there may be a definite fraction for $n \rightarrow \infty$. How could this fraction be calculated? - Before delving into this: Are there further simple necessary conditions for a sequence to be a hyper-degree sequence? For example, for $k=2$ there must be at least $\alpha$ nodes $i \neq 1$ with $a_i \geq 1$ when $a_1 = \alpha$. - Finally: How do I construct a $k$-uniform hypergraph for a given hyper-degree sequence? [1]: https://math.stackexchange.com/a/3788911/1792 [2]: https://math.stackexchange.com/questions/3788654/reconstructing-sets-of-sets-from-reduced-membership-information [3]: https://en.wikipedia.org/wiki/Hypergraph [4]: http://www.google.com/search?q=%22hyper-degree%20sequence%22 [5]: https://en.wikipedia.org/wiki/Handshaking_lemma