Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|improve this answer
add comment

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

share|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 arxiv.org/abs/math/0610787 –  Gjergji Zaimi Sep 12 '12 at 1:51
add comment

Your Answer

 
discard

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.