Degree sequences in complexes and hypergraphs

Abstract:

Given an $n$-complex $K$ and a vertex $v$ in $K$, the $n$-degree of $v$ is the number of $n$-simplexes in $K$ containing $v$. The set of all $n$-degrees in a complex $K$ is called its $n$-degree sequence when arranged in nonincreasing order. The question “Which sequences of integers are $n$-degree sequences?” is answered in this paper. This is done by generalizing the iterative characterization for the $1$-dimensional (graphical) case due to V. Havel. A corollary to this general theorem yields the analogous generalization for $k$-graphs. The characterization of P. Erdös and T. Gallai is discussed briefly.