20
$\begingroup$

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 + \dotsb$, 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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$ Sep 12, 2012 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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