# Is there an analogue of the Erdős–Gallai theorem for simplicial complexes?

The Erdős–Gallai theorem gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph.

In particular $d_1 \ge d_2 \ge \dots \ge d_n$ is the degree sequence of a graph on $n$ vertices if and only if

(1) $d_1 + d_2 + \dots d_n$ is even, and

(2) $$\sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n\min (d_i, k)$$

holds for $1 \le k \le n$.

Now let $\Delta$ be a $k$-dimensional simplicial complex on $n$ vertices, with a complete $(k-1)$-skeleton. I.e. $$f_{k-1} (\Delta) = {n \choose k}$$

The degree of a $(k-1)$-dimensional face of $\Delta$ is defined to be the number of $k$-dimensional faces containing it.

What are the possible degree sequences $$d_1 \ge d_2 \ge \dots \ge d_{n \choose k}?$$

Clearly a necessary condition is that $(k+1)$ divides the sum $d_1 + d_2 + \dots$, but is there something analogous to condition (2) above that makes this into necessary and sufficient conditions?

Is the Kruskal-Katona theorem of any help?

-

Very little is known about the question (and even about the easier case of vertex degrees), and it contains as a special case some notoriously hard questions: For example the case that all $d_i$s are equal to 1 (or to some $\lambda$ is the question on the existence of combinatorial designs of certain parameters. I suppose that even checking if a sequence is a dgree sequence is computationally intractable, for large values of $d$ but I am not sure about that.