MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer

Yes. A.K. Dewdney Degree sequences in complexes and hypergraphs, PAMS, 1975.

share|cite|improve this answer
This paper deals with vertex degrees instead of subfacet degrees, which the OP is asking about. Also it talks about a generalization of Havel-Hakimi, not Erdos-Gallai. As far as I know very little is known in this direction. See this more recent paper – Gjergji Zaimi Sep 12 '12 at 1:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.