Partial Shadows of Set Systems. (20th January 2015)

• Record Type: Journal Article
• Authors: BOLLOBÁS, BÉLA; ECCLES, TOM
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 5(2015:Sep.)
• Page Start: 825
• Page End: 828
• Publication Date: 2015-01-20
• Subjects: Primary 05D05 (Extremal set theory), -- Secondary 05A99 (Enumerative combinatorics); Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000790
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : The shadow of a system of sets is all sets which can be obtained by taking a set in the original system, and removing a single element. The Kruskal-Katona theorem tells us the minimum possible size of the shadow of $\mathcal A$, if $\mathcal A$ consists of m r -element sets. In this paper, we ask questions and make conjectures about the minimum possible size of a partial shadow for $\mathcal A$, which contains most sets in the shadow of $\mathcal A$ . For example, if $\mathcal B$ is a family of sets containing all but one set in the shadow of each set of $\mathcal A$, how large must $\mathcal B$ be?