MATH Seminar

Title: Erdos-Ko-Rado-type colorings of systems of sets or linear spaces
Seminar: Combinatorics
Speaker: Hanno Lefmann of Chemnitz University of Technology
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2012-02-24 at 4:00PM
Venue: W306
Download Flyer
Abstract: For a family $F$ of $r$-sets in an $n$-sets elements, we consider colorings of $F$ with $k$ colors such that each two $r$-sets in $F$ of the same color must intersect in at least $\ell$ vertices, $\ell < r$. In particular, we are interested in the structure of such families that maximize these number of colorings. It turns out that for $k=2$ or $k=3$ colors, the solution of this problem is related to the Erdos-Ko-Rado theorem (or the Tur\'an number of the corresponding uncolored problem). Also the case of more than $3$ colors will be discussed. Moreover, we address a $q$-analogue of this question, i.e., the intersection of each two linear $r$-subspaces of the same color in a family $F$ must have dimension at least $\ell$.