Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T06:33:21.170Z Has data issue: false hasContentIssue false

Partial Shadows of Set Systems

Published online by Cambridge University Press:  20 January 2015

BÉLA BOLLOBÁS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected]) Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: [email protected])
TOM ECCLES
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])

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?

Type
Paper
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Katona, G. O. H. (1968) A theorem of finite sets. In Theory of Graphs (Erdős, P. and Katona, G. O. H., eds), Conference in Tihany, Hungary, 1966, Academic Press and Akadémiai Kiadó, pp. 187207.Google Scholar
[2] Kruskal, J. B. (1963) The number of simplices in a complex. In Mathematical Optimization Techniques, University of California Press, pp. 251278.Google Scholar
[3] Lovász, L. (1979) Combinatorial Problems and Exercises, North-Holland.Google Scholar