Department Colloquium

Location: RI 209

Speaker: Denys Bulavka, Dalhousie University

Title:  Erdős-Ko-Rado type problems

Abstract:

A set family \(F\) is pairwise-intersecting if every pair of its members intersect. In 1960, Erdős, Ko, and Rado gave an upper-bound on the size of a pairwise-intersecting family of \(k\)-sets coming from a ground set of size \(n\). Moreover, they characterized the families achieving the upper-bound. These are families whose members all share exactly one element, so called trivial families. Later, Hilton and Milner provided the next best upper-bound for pairwise-intersecting families that are not trivial.

There are several generalizations of the above results. If time allows, we will go over two of such generalizations.

First, we will focus on the case when the set family is replaced with a subspace of the exterior algebra. In this scenario intersection is replaced with the wedge product, being pairwise-intersecting with self-annihilating and being trivial with being annihilated by a 1-form. Scott and Wilmer, and Woodroofe gave an upper-bound on the dimension of self-annihilating subspaces of the exterior algebra. In the current talk we will see that the better upper-bound coming from Hilton and Milner’s theorem holds for non-trivial self-annihilating subspaces.

Second, going back to set systems, Chvátal conjectured in the 1960s that the largest (non-uniform) pairwise-intersecting family in any hereditary family is given by a star. Recently, Holroyd, Talbot, and Borg extended this conjecture to uniform families. In the second part of this talk I will share some progress towards this conjecture. In particular it validity for a large class of hereditary families known as sequentially Cohen-Macaulay near-cones, e.g., the independence complex of a chordal graph that has an isolated vertex.

This talk is based on joint works with Francesca Gandini and Russ Woodroofe.