An inequality for Kruskal-Macaulay functions

Abstract

Given integers $k\ge 1$ and $n\ge 0$, there is a unique way of writing $n$ as $n=\left(\genfrac{}{}{0ex}{}{n_k}{k}\right)+\left(\genfrac{}{}{0ex}{}{n_{k-1}}{k-1}\right)+...+\left(\genfrac{}{}{0ex}{}{n_1}{1}\right)$ so that $0\le n_1<...<n_{k-1}<n_k$. Using this representation, the \emph{Kruskal-Macaulay function of}$n$ is defined as $\partial^{k}(n) =\binom{n_{k}-1}{k-1}+\binom{n_{k-1}-1}{k-2}+...+\binom{n_{1}-1}% {0}.$ We show that if $a\ge 0$ and $a<{\partial }^{k+1}(n)$, then ${\partial }^k(a)+{\partial }^{k+1}(n-a)\ge {\partial }^{k+1}(n).$ As a corollary, we obtain a short proof of Macaulay's Theorem. Other previously known results are obtained as direct consequences.

February 9th, 2009 version. The introduction was improved. Theorem 1 now establishes equality for some $n$. Corollary 2 (Björner and Vrećica Theorem) was added. Acknowledgements were added