From an answer to this question I have learned how to ask this question properly.

Consider a $k$-uniform hypergraph 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 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 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?