Multidimensional Kruskal-Katona Theorem
Multidimensional Kruskal-Katona Theorem
复制标题
多维克鲁斯卡-卡托纳定理
DOI：
10.1137/100808630
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Bukh
中科院分区：
文献类型：
--
作者：
B. Bukh
We present a generalization of a version of the Kruskal–Katona theorem due to Lovasz. A shadow of a d-tuple $(S_1,\dots,S_d)\in\binom{X}{r}^d$ consists of d-tuples $(S_1',\dots,S_d')\in\binom{X}{r-1}^d$ obtained by removing one element from each of the $S_i$. We show that if a family $\mathcal{F}\subset\binom{X}{r}^d$ has size $|\mathcal{F}|=\binom{x}{r}^d$ for a real number $x\geq r$, then the shadow of $\mathcal{F}$ has size at least $\binom{x}{r-1}^d$.
We present a generalization of a version of the Kruskal–Katona theorem due to Lovasz. A shadow of a d-tuple $(S_1,\dots,S_d)\in\binom{X}{r}^d$ consists of d-tuples $(S_1',\dots,S_d')\in\binom{X}{r-1}^d$ obtained by removing one element from each of the $S_i$. We show that if a family $\mathcal{F}\subset\binom{X}{r}^d$ has size $|\mathcal{F}|=\binom{x}{r}^d$ for a real number $x\geq r$, then the shadow of $\mathcal{F}$ has size at least $\binom{x}{r-1}^d$.