Skip to main content
2 of 2
fixed broken links to Wikipedia; used Markdown list formatting; \dots -> \dotsb

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 + \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?

Matthew Kahle
  • 7.9k
  • 1
  • 39
  • 67