Multidimensional Kruskal-Katona theorem

2010/09/13 by Boris Bukh, Bukh, Boris
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D05

paper · pdf · doi:10.48550/arxiv.1009.2375

8 pages, 1 figure, typos fixed

arxiv created 2011/11/06 · arxiv updated 2011/11/08

Abstract

We present a generalization of a version of the Kruskal-Katona theorem due to Lovasz. A shadow of a d-tuple (S₁,...,S_d) in binomXr^d consists of d-tuples (S₁',...,S_d') in binomXr-1^d obtained by removing one element from each of S_i. We show that if a family F in binomXr^d has size |F|=binomxr^d for a real number x>=r, then the shadow of F has size at least binomxr-1^d.

Related

• Kruskal-Katona type Problem
• Extremal families for the Kruskal--Katona theorem
• Shadows of 3-uniform hypergraphs under a minimum degree condition
• Tight bounds for Katona's shadow intersection theorem
• A grid generalisation of the Kruskal-Katona theorem