Combinatorics in the exterior algebra and the two families theorem

Combinatorics in the exterior algebra and the two families theorem

-
Alex Scott, University of Oxford

The two families theorem of Bollobas says the following: Let (A_i,B_i) be a sequence of pairs of sets such that the A_i have size a, the B_i have size b, and A_i and B_j intersect if and only if i and j are distinct. Then the sequence has length at most \binom{a+b}{a}.

This beautiful result has many applications and has been generalized in two distinct ways. The first (which follows from the original result of Bollobas) allows the sets to have different sizes, and replaces the cardinality constraint with a weighted sum. The second uses an elegant exterior algebra argument due to Lovasz and allows the intersection condition to be replaced by a skew intersection condition. However, there are no previous results that have versions of both conditions.

In this talk, we will explain and extend the exterior algebra approach. We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hypergraphs. As an application, we prove a new extension of the two families theorem that allows both (some) variation in set sizes and a skew intersection condition.

This is joint work with Elizabeth Wilmer (Oberlin).