Compatibility bound for complementary generating families

ID: compatibility-bound-for-complementary-generating-families

Let and let generate respectively a t-intersecting family of -sets and its complement family. If their union had size at most , contain it in a set of that size. Since , extend within to an -set and an -set . Both and belong to the original family, but . This contradiction proves the bound.

New to topics? Read the docs here!