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

The Erdős–Gallai theoremErdő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$.

  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$$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 theoremKruskal–Katona theorem of any help?

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?

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?

Source Link
Matthew Kahle
  • 7.9k
  • 1
  • 39
  • 67

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?