This file defines UV-compression. It is an operation on a set family that reduces its shadow.
a : α along
u v : α means replacing
(a ⊔ u) \ v if
v ≤ a. In some sense, it's moving
UV-compressions are immensely useful to prove the Kruskal-Katona theorem. The idea is that compressing a set family might decrease the size of its shadow, so iterated compressions hopefully minimise the shadow.
Main declarations #
compress u v ais
compression u v sis the compression of the set family
v. It is the compressions of the elements of
swhose compression is not already in
salong with the element whose compression is already in
s. This way of splitting into what moves and what does not ensures the compression doesn't squash the set family, which is proved by
𝓒 (typed with
\MCC) is notation for
uv.compression in locale
Prove that compressing reduces the size of shadow. This result and some more already exist on the
compression, UV-compression, shadow
UV-compression in generalized boolean algebras #
a, if it doesn't touch
U and does contain
V, we remove
U in. We'll only really use this when
|U| = |V| and
U ∩ V = ∅.
To UV-compress a set family, we compress each of its elements, except that we don't want to reduce the cardinality, so we keep all elements whose compression is already present.
a is in the UV-compressed family iff it's in the original and its compression is in the
original, or it's not in the original but it's the compression of something in the original.
a is in the family compression and can be compressed, then its compression is in the
a is in the
u, v-compression but
v ≤ a, then
a must have been in the original